perm filename V2P.IN[TEX,DEK] blob sn#360779 filedate 1977-05-28 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	folio 687 galley 1
C00019 00003	folio 690 galley 2
C00034 00004	folio 693 galley 3
C00050 00005	folio 701 galley 4
C00064 00006	folio 707 galley 5
C00079 00007	folio 710 galley 6
C00093 00008	folio 715 galley 7
C00107 00009	folio 717 galley 8
C00121 00010	folio 720 galley 9
C00134 00011	folio 722 galley 10
C00144 ENDMK
C⊗;
folio 687 galley 1
    0  {U0}{H10L12M29}W58320#Computer Programming|9(Knuth/Addison-W
    1  esley)|9f. 687|9answers|9g. 1a|'{A6}{H9L11}|πThe 
    5  value for a truly random sequence is |εe|4α_↓|41; 
   13  |πour value is |εe|4α_↓|41|4α+↓|4(e/2|4α_↓|41)/a|4α+↓|4O(1/a
   16  |g2). Note|*/: |\|πThe same result holds for an 
   24  ascending run, since |εU|βn|4|¬R|4U|βn|βα+↓|β1 
   28  |πif and only if |ε1|4α_↓|4U|βn|4|¬W|41|4α_↓|4U|βn|βα+↓|β1. 
   33  |πThis would lead us to suspect that run lengths 
   42  in linear congruential dequences tend to be slightly 
   50  longer than normal, so the run test should be 
   59  applied to such generators.|'{A3}|≡2|≡5|≡.|9|4|πLet 
   64  |εk|β0|4α=↓|4|"pa|≤a|4α+↓|4|≤U|4α_↓|4|≤b|¬S|"P, 
   65  k|β1|4α=↓|4|"pa|≤b|4α+↓|4|≤U|4α_↓|4|≤b|¬S|"P. 
   66  x |πmust be in the intervals [(|εk|4α+↓|4|≤a|¬S|4α_↓|4|≤U)/a
   72  , (k|4α+↓|4|≤b|¬S|4α_↓|4|≤U)/a) |πfor some |εk, 
   77  |πand also in the interval [|ε|≤a,|4|≤b). |πWith 
   84  due regard to boundary conditions, we get the 
   92  probability|'{A9}{M29}(|εk|β1|4α_↓|4k|β0)(|≤b|¬S|4α_↓|4|≤a|¬
   93  S)/a|4α+↓|4|πmax{H12}({H9}0,|4|ε|≤b|4α_↓|4(k|β1|4α+↓|4|≤a|¬S
   93  |4α_↓|4|≤U)/a{H12}){H10}|4α_↓|4|πmax{H11}({H9}|ε0,|4|≤a|4α_↓
   93  |4(k|β0|4α+↓|4|≤a|¬S|4α_↓|4|≤U)/a{H12}){H9}.|'
   94  {A9}{M29}|πThis is (|ε|≤b|4α_↓|4|≤a)(|≤b|¬S|4α_↓|4|≤a|¬S)|4α
   96  +↓|4|≤e, |πwhere |¬G|ε|≤e|¬G|4|¬W|42(|≤b|¬S|4α_↓|4|≤a|¬S)/a.
   98  |'{A6}{M12.6}|π|≡F|≡i|≡g|≡.|4|4|≡A|≡<|≡1|≡.|9|4Permutation 
  100  regions for Fibonacci generator.|'{A6}|≡F|≡i|≡g|≡.|4|4|≡A|≡<
  104  |≡2|≡.|9|4Run-length regions for Fibonacci generator.|'
  109  {A6}{M29}|≡2|≡6|≡.|9|4See Fig. A<1; the orderings 
  114  |εU|β1|4|¬W|4U|β3|4|¬W|4U|β2 |πand |εU|β2|4|¬W|4U|β3|4|¬W|4U
  116  |β1 |πare impossible; the other four each have 
  124  probability |f1|d34|).|'{A3}|≡2|≡7|≡.|9|4|εU|βn|4α=↓|4(F|βn|
  126  βα_↓|β1U|β0|4α+↓|4F|βnU|β1)|πmod 1. We need |εF|βk|βα_↓|β1U|
  130  β0|4α+↓|4F|βkU|β1|4|¬W|41 |πand |εF|βkU|β0|4α+↓|4F|βk|βα+↓|β
  132  1U|β1|4|¬Q|41. |πThe half-unit-square in whihc 
  137  |εU|β0|4|¬Q|4U|β1 |πis broken up as shown in 
  144  Fig. A<2, with various values of |εk |πindicated. 
  152  The probability for a run of length |εk |πis 
  161  |f1|d32|) if |εk|4α=↓|41; 1/F|βk|βα_↓|β1F|βk|βα+↓|β1|4α_↓|41
  164  /F|βkF|βk|βα+↓|ε|β2, |πif |εk|4|¬Q|41. |πThe 
  168  corresponding probabilities for a random sequence 
  174  are |ε2k(k||L!!!!!!!|εk:|L1|L|32|L|33|L|74|L|5|55>
  176  {A2}|L|πProbability|6in|6Fibonacci|6case:|L|f1|d32|)|L|4|f1|
  176  d33|)|L|f1|d310|)|L|4|f1|d324|)|L|4|4|f1|d365|)>
  177  |LProbability|6in|6random|6case:|L|f1|d33|)|L|f5|d312|)|L|f1
  177  1|d360|)|L|f19|d3360|)|L|f29|d32520|)>{A9}|≡2|≡8|≡.|9|4Fig. 
  179  A<3 shows the various regions in the general 
  187  case. The ``213'' region means |εU|β2|4|¬W|4U|β1|4|¬W|4U|β3,
  192   |πif |εU|β1 |πand |εU|β2 |πare chosen at random; 
  201  the ``321'' region means |εU|β3|4|¬W|4U|β2|4|¬W|4U|β1, 
  206  |πetc., The probabilities for 123 and 321 are 
  214  |f1|d34|)|4α_↓|4|ε|≤a/2|4α+↓|4|≤a|g2/2; |πthe 
  216  probabilities for all other cases are |f1|d38|)|4α+↓|4|ε|≤a/
  222  4|4α_↓|4|≤a|g2/4. |πto have all equal to |f1|d36|), 
  229  we must have |f1|d34|)|4α_↓|4|ε|≤a/2|4α+↓|4|≤a|g2/2|4α=↓|4|f
  232  1|d38|)|4α+↓|4|≤a/4|4α_↓|4|≤a|g2/4, |πthat is, 
  235  |ε1|4α_↓|46|≤a|4α+↓|46|≤a|g2|4α=↓|40. The result 
  238  of this exercise gives a simple proof of a theorem 
  248  due to J. Franklin (|εMath. comp. |π|≡1|≡7 (1963), 
  256  28<59, Theorem 13); other results of that paper 
  264  are related to exercises 22 and 23.]|'{A6}|≡F|≡i|≡g|≡.|4|4|≡
  271  A|≡<|≡3|≡.|9|4Permutation regions for a generator 
  276  with a potency of 2; |ε|≤a|4α=↓|4(a|4α_↓|41)c/m.|;
  282  {A6}{H10L12}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨3|∨.|∨3|∨.|∨4|'
  283  {A12}{H9L11}|5|5|≡1|≡.|9|4|ε|≤n|β1 |πis always 
  286  |εm |πand |ε|≤m|β1|4α=↓|42, |πfor generators 
  291  of maximum period.|'{A3}|5|5|≡2|≡.|9|4|πLet |εV 
  296  |πbe the matrix whose rows are |εv|β1,|4.|4.|4.|4,|4v|βt. 
  303  |πTo minimize |εY|4|¬O|4Y, |πsubject to the condition 
  310  that |εY|4α=↓|4(0,|4.|4.|4.|4,|40) |πand |εVY 
  314  |πis an integer column vector |εX, |πis equivalent 
  322  to minimizing (|εV|gα_↓|g1X)|4|¬O|4(V|gα_↓|g1X), 
  325  |πsubject to the condition that |εX |πis a nonzero 
  334  integer column vector. The columns of |εV|gα_↓|g1 
  341  |πare |εU|β1,|4.|4.|4.|4,|4U|βt.|'{A3}|5|5|≡3|≡.|9|4|εa|g2|4
  343  |¬7|42a|4α_↓|41 |πand |εa|g3|4|¬7|43a|4α_↓|42 
  346  (|πmodulo |εm). |πBy considering all short solutions 
  353  of (15), we _nd that |ε|≤n|=|β3|g2|4α=↓|46 |πand 
  360  |ε|≤n|=|β4|g2|4α=↓|44, |πfor the respective vectors 
  365  (1,|4|→α_↓2,|41) and (1,|4|→α_↓1,|4|→α_↓1,|41), 
  368  except in the following cases: |εm|4α=↓|42|geq, 
  374  q |πodd, |εe|4|¬R|43, a|4|¬7|42|ge|gα_↓|g1 (|πmodulo 
  379  2|ge), |εa|4|¬7|41 (modulo |εq), |≤n|=|β3|g2|4α=↓|4|≤n|=|β4|
  383  g2|4α=↓|42; m|4α=↓|43|geq, |πgcd(|ε3,|4q)|4α=↓|41, 
  386  e|4|¬R|42, a|4|¬7|41|4|¬9|43|ge|gα_↓|g1 (|πmodulo 
  389  |ε3|ge), a|4|¬7|41 (|πmodulo |εq), |≤n|=|β4|g2|4α=↓|42; 
  394  m|4α=↓|49, a|4α=↓|44 or 7, |ε|≤n|=|β2|g2|4α=↓|4|≤n|=|β3|g2|4
  398  α=↓|45.|'{A3}|5|5|≡4|≡.|9|4(|πa) The unique choice 
  403  for (|εx|β1,|4x|β2) |πis |ε|f1|d3m|)(y|β1u|β2|β2|4α_↓|4y|β2u
  406  |β2|β1, |→α_↓y|β1u|β1|β2|4α+↓|4y|β2u|β1|β1), 
  408  |πand this is |→|¬7|2|f1|d3|εm|)(y|β1u|β2|β2|4α+↓|4y|β2au|β2
  411  |β2, |→α_↓y|β1u|β1|β2|4α_↓|4y|β2au|β1|β2)|4|¬7|4(0,|40) 
  413  (|πmodulo 1); i.e., |εx|β1 |πand |εx|β2 |πare 
  420  integers. (b) When (|εx|β1,|4x|β2)|4|=|↔6α=↓|4(0,|40), 
  424  |πwe have (|εx|β1u|β1|β1|4α+↓|4x|β2u|β2|β1)|g2|4α+↓|4(x|β1u|
  426  β1|β2|4α+↓|4x|β2u|β2|β2)|g2|4α=↓|4x|=|β1|g2(u|=|β1|g2|β1|4α+
  426  ↓|4u|=|β1|g2|β2)|4α+↓|4x|=|β2|g2(u|=|β2|g2|β1|4α+↓|4|=|β2|g2
  426  |β2)|4α+↓|42x|β1x|β2(u|β1|β1u|β2|β1|4α+↓|4u|β1|β2u|β2|β2)|4|
  426  ¬R|4(x|=|β1|g2|4α+↓|4x|=|β2|g2|4α_↓|4|¬Gx|β1x|β2|¬G)(u|=|β1|
  426  g2|β1|4α+↓|4u|=|β1|g2|β2)|4|¬R|4u|=|β1|g2|β1|4α+↓|4u|=|β1|g2
  426  |β2. [|πNote that this si a stronger result than 
  435  Lemma A, which tells us only that |εx|=|β1|g2|4|¬E|4(u|=|β1|
  442  g2|β1|4α+↓|4u|=|β1|g2|β2)(u|=|β2|g2|β1|4α+↓|4u|=|β2|g2|β2)/m
  442  |g2, x|=|β2|g2|4|¬E|4(u|=|β1|g2|β1|4α+↓|4u|=|β1|g2|β2)|g2/m|
  443  g2, |πand the latter can be |→|¬R1. The idea 
  452  is essentially Gauss's notion of a reduced binary 
  460  quadratic form, |εDisq. Arith. (Leipzig, 1801), 
  466  |πSection 171.]|'{A3}|5|5|≡5|≡.|9|4Conditions 
  469  (30) remain invariant; hence |εh |πcannot be 
  476  zero in step S2, when |εa |πis relatively prime 
  485  to |εm. |πSince |εh |πalways decreases in that 
  493  step, S2 eventually terminates with |εu|g2|4α+↓|4v|g2|4|¬R|4
  498  s. |πNote that |εpp|¬S|4|¬E|40 |πthroughout the 
  504  calculation.|'!|9|7The hinted inequality surely 
  509  holds the _rst time step S2 is done. The integer 
  519  |εq|¬S |πwhich minimizes (|εh|¬S|4α_↓|4qh)|g2|4α+↓|4(p|¬S|4α
  522  _↓|4q|¬Sp)|g2 |πis |εq|¬S|4α=↓|4|πround{H11}({H9}h|¬Sh|4α+↓|
  524  4|εp|¬Sp)/(h|g2|4α+↓|4p|g2){H12}){H9L11}), |πby 
  526  (24). If (|εh|¬S|4α_↓|4q|¬Sh)|g2|4α+↓|4(p|¬S|4α_↓|4q|¬Sp)|g2
  528  |4|¬W|4h|g2|4α+↓|4p|g2 |πwe must have |εq|¬S|4|=|↔6α=↓|40, 
  533  q|¬S|4|=|↔6α=↓|4|→α_↓1, |πhence (|εp|¬S|4α_↓|4q|¬Sp)|g2|4|¬R
  535  |4p|g2, |πhence (|εh|¬S|4α_↓|4q|¬Sh)|g2|4|¬W|4h|g2, 
  538  |πi.e., |¬G|εh|¬S|4α_↓|4q|¬Sh|¬G|4|¬W|4h, |πi.e. 
  541  |εq|¬S|4α=↓|4q |πor |εq|4α+↓|41. |πWe have |εhu|4α+↓|4pv|4|¬
  546  R|4h(h|¬S|4α_↓|4q|¬Sh)|4α+↓|4p(p|¬S|4α_↓|4q|¬Sp)|4|¬R|4|→α_↓
  546  |f1|d32|)(h|g2|4α+↓|4p|g2), |πso if |εu|g2|4α+↓|4v|g2|4|¬W|4
  549  s |πthe next iteration of step S2 will preserve 
  558  the assumption in the hint. If |εu|g2|4α+↓|4v|g2|4|¬R|4s|4|¬
  564  Q|4(u|4α_↓|4h)|g2|4α+↓|4(v|4α_↓|4p)|g2, |πwe 
  566  have 2|¬G|εh(u|4α_↓|4h)|4α+↓|4p(v|4α_↓|4p)|¬G|4α=↓|42{H11}){
  567  H9}h(h|4α_↓|4u)|4α+↓|4p(p|4α_↓|4v){H12}){H9}α=↓|4(|εu|4α_↓|4
  567  h)|g2|4α+↓|4(v|4α_↓|4p)|g2|4α+↓|4h|g2|4α+↓|4p|g2|4α_↓|4(u|g2
  567  |4α+↓|4v|g2)|4|¬E|4(u|4α_↓|4h)|g2|4α+↓|4(v|4α_↓|4p)|g2|4|¬E|
  567  4h|g2|4α+↓|4p|g2, |πhence (|εu|4α_↓|4h)|g2|4α+↓|4(v|4α_↓|4p)
  569  |g2 |πis minimal by exercise 4. Finally if both 
  578  |εu|g2|4α+↓|4v|g2 |πand (|εu|4α_↓|4h)|g2|4α+↓|4(v|4α_↓|4p)|g
  580  2 |πare |→|¬R|εs, |πlet |εu|¬S|4α=↓|4h|¬S|4α_↓|4q|¬Sh, 
  585  v|¬S|4α=↓|4p|¬S|4α_↓|4q|¬Sp; |πthen 2|¬G|εhu|¬S|4α+↓|4pv|¬S|
  587  ¬G|4|¬E|4h|g2|4α+↓|4p|g2|4|¬E|4u|¬S|g2|4α+↓|4v|¬S|g2, 
  588  |πand |εh|g2|4α+↓|4p|g2 |πis minimal by exercise 
  594  4.|'{A3}|5|5|≡6|≡.|9|4|πIf |εu|g2|4α+↓|4v|g2|4|¬R|4s|4|¬Q|4(
  596  u|4α_↓|4h)|g2|4α+↓|4(v|4α_↓|4p)|g2 |πin the previous 
  600  answer, we have (|εv|4α_↓|4p)|g2|4|¬Q|4v|g2, 
  604  |πhence (|εu|4α_↓|4h)|g2|4|¬W|4u|g2; |πand if 
  608  |εq|4α=↓|4a|βj, |πso that |εh|¬S|4α=↓|4a|βjh|4α+↓|4u, 
  612  |πwe must have |εa|βj|βα+↓|β1|4α=↓|41. |πIt follows 
  618  that |ε|≤n|=|β2|g2|4α=↓|4|πmin|ε|β0|β|¬E|βj|β|¬W|βt(m|=|βj|g
  619  2|4α+↓|4p|ur2|)jα_↓1|)), |πin the notation of 
  624  exercise 3.3.3<16.|'!|9|7Now |εm|β0|4α=↓|4m|βjp|βj|4α+↓|4m|β
  627  j|βα+↓|β1p|βj|βα_↓|β1|4α=↓|4a|βjm|βjp|βj|βα_↓|β1|4α+↓|4m|βjp
  627  |βj|βα_↓|β2|4α+↓|4m|βj|βα+↓|β1p|βj|βα_↓|β1|4|¬W|4(a|βj|4α+↓|
  627  41|4α+↓|41/a|βj)m|βjp|βj|βα_↓|β1|4|¬E|4(A|4α+↓|41|4α+↓|41/A)
  627  m|βjp|βj|βα_↓|β1, |πand |εm|=|βj|g2|4α+↓|4p|ur2|)jα_↓1|)|4|¬
  629  R|42m|βjp|βj|βα_↓|β1, |πhence the result.|'{A3}|5|5|≡7|≡.|9|
  633  4We shall prove, using condition (19), that |εU|βj|4|¬O|4U|β
  640  k|4α=↓|40 |πfor all |εk|4|=|↔6α=↓|4j |πi= |εV|βj|4|¬O|4V|βk|
  645  4α=↓|40 |πfor all |εk|4|=|↔6α=↓|4j. |πAssume 
  650  that |εU|βj|4|¬O|4U|βk|4α=↓|40 |πfor all |εk|4|=|↔6α=↓|4j, 
  655  |πand let |εU|βj|4α=↓|4|≤a|β1V|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4
  657  |≤a|βtV|βt. |πThen |εU|βj|4|¬O|4U|βk|4α=↓|4|≤a|βk 
  660  |πfor all |εk, |πhence |εU|βj|4α=↓|4|≤a|βjV|βj, 
  665  |πand |εV|βj|4|¬O|4V|βk|4α=↓|4|≤a|urα_↓1|)j|)(U|βj|4|¬O|4V|β
  666  k)|4α=↓|40 |πfor all |εk|4|=|↔6α=↓|4j. |πA symmetric 
  672  argument proves the converse.|'{A3}|5|5|≡8|≡.|9|4Clearly 
  677  |εv|βt|βα+↓|β1|4|¬E|4|≤n|βt (|πa fact used implicitly 
  682  in Algorithm S, since |εs |πis not changed when 
  691  |εt |πincreases). For |εt|4α=↓|42 |πthis is equivalent 
  698  to (|εm|≤m|β2/|≤p)|g1|g/|g2|4|¬R|4(|f3|d34|)m|≤m|β3/|≤p)|g1|
  699  g/|g3, |πi.e., |ε|≤m|β3|4|¬E|4|f4|d33|)|2|¬H|v4m/|≤p|)|4|≤m|
  701  ur3/2|)2|). |πThis reduces to |f4|d33|)|310|gα_↓|g4/{H11}|¬H
  705  {H10}|v4|ε|≤p|) |πwith the given parameters, 
  710  but for large |εm |πand _xed |ε|≤m|β2 |πthe{U0}{H10L12M29}W5
folio 690 galley 2
  717  8320#Computer Programming|9(Knuth/Addison-Wesley)|9f. 
  719  690|9Answers|9g. 2a|'{A6}{H9L11M29}|5|5|≡9|≡.|9|4Let 
  722  |εf|1(y|β1,|4.|4.|4.|4,|4y|βt)|4α=↓|4|≤u; |πthen 
  724  gcd(|εy|β1,|4.|4.|4.|4,|4y|βt)|4α=↓|41, |πso 
  726  there is an integer matrix |εW |πof determinant 
  734  1 having (|εw|β1,|4.|4.|4.|4,|4w|βt) |πas its 
  739  _rst row. (Prove the latter fact by induction 
  747  on the magnitude of the smallest nonzero entry 
  755  in the row.) Now if |εX|4α=↓|4(x|β1,|4.|4.|4.|4,|4x|βt) 
  761  |πis a row vector, we have |εXW|4α=↓|4X|¬|¬S 
  768  |πi= |εX|4α=↓|4X|¬SW|gα_↓|g1, |πand |εW|1|gα_↓|g1 
  772  |πis an integer matrix of determinant 1, hence 
  780  the form |εg |πde_ned by |εWU |πsatis_es |εg(x|β1,|4.|4.|4.|
  787  4,|4x|βt)|4α=↓|4f|1(x|=|β1|¬S,|4.|4.|4.|4,|4x|=|βt|¬S); 
  788  |πfurthermore |εg(1,|40,|4.|4.|4.|4,|40)|4α=↓|4|≤u.|'
  790  !!|2|πWithout loss of generality, assume that 
  796  |εf|4α=↓|4g. |πIf now |εS |πis any orthogonal 
  803  matrix, the matrix |εUS |πde_nes the same form 
  811  as |εU, |πsince (|εXUS)(XUS)|gT|4α=↓|4(XU)(XU)|gT. 
  815  |πChoosing |εS |πso that its _rst column is a 
  824  multiple of |εV|β1 |πand its other columns are 
  832  any suitable vectors, we have|'{A6}|h|πUS|4α=↓|4|7|∂|9|ε|≤a|
  837  β1|9|∂|9|≤a|β2|4.|4.|4.|4|≤a|βt|9|∂|E|n|;|>|;
  840  |ε|≤a|β1|;|≤a|β2|4.|4.|4.|4|≤a|βt|;>{A4}|>|;0|;
  846  >|>|;|¬O|;>|>|πUS|4α=↓|4|7|?|¬O|;|εU|¬S|;>|>|;
  858  |¬O|;>|>|;0|;>{A6}|πfor some |ε|≤a|β1,|4|≤a|β2,|4.|4.|4.|4,|
  866  4|≤a|βt |πand some (|εt|4α_↓|41)|4α⊗↓|4(t|4α_↓|41) 
  870  |πmatrix |εU|¬S. |πHence |εf|1(x|β1,|4.|4.|4.|4,|4x|βt)|4α=↓
  873  |4(|≤a|β1x|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|≤a|βtx|βt)|g2|4α+↓|
  873  4h(x|β2,|4.|4.|4.|4,|4x|βt). |πIt follows that 
  877  |ε|≤x|β1|4α=↓|4{H11}|¬H{H9}|v4|≤u|) [|πin fact, 
  880  |ε|≤x|βj|4α=↓|4(U|β1|4|¬O|4U|βj)/{H11}|¬H{H9}|v4|≤u|) 
  881  |πfor |ε1|4|¬E|4j|4|¬E|4t], |πand that |εh |πis 
  887  a positive de_nite quadratic form de_ned by |εU|¬S, 
  895  |πwhere det |εU|¬S|4α=↓|4(|πdet|4|εU)/{H11}|¬H{H9}|v4|≤u|). 
  898  |πBy induction on |εt, |πthere are integers (|εx|β2,|4.|4.|4
  905  .|4,|4x|βt) |πwith |εh(x|β2,|4.|4.|4.|4,|4x|βt)|4|¬E|4(|f4|d
  907  33|))|g(|gt|gα_↓|g2|g)|g/|g2|2|¬G|πdet|4|εU|¬G|g2|g/|g(|gt|g
  907  α_↓|g1|g)/|≤u|g1|g/|g(|gt|gα_↓|g1|g), |πand for 
  910  these integer values we can choose |εx|β1 |πso 
  918  that |¬G|εx|β1|4α+↓|4(|≤a|β2x|β2|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|
  919  ≤a|βtx|βt)/|≤a|β1|¬G|4|¬E|4|f1|d32|), |πi.e., 
  921  (|ε|≤a|β1x|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|≤a|βtx|βt)|g2|4|¬E|
  921  4|f1|d34|)|≤u. |πHence |ε|≤u|4|¬E|4|εf|1(x|β1,|4.|4.|4.|4,|4
  923  x|βt)|4|¬E|4|f1|d34|)|≤u|4α+↓|4(|f4|d33|))|g(|gt|gα_↓|g2|g)|
  923  g/|g2|2|¬G|πdet|4|εU|¬G|g2|g/|g(|gt|gα_↓|g1|g)/|≤u|g1|g/|g(|
  923  gt|gα_↓|g1|g) |πand the desired inequality follows 
  929  immediately.|'!!|2[For |εt|4α=↓|42 |πthe result 
  934  is best possible. For general |εt, |πHermite's 
  941  theorem implies that |ε|≤m|βt|4|¬E|4|≤p|gt|g/|g2(4/3)|gt|g(|
  944  gt|gα_↓|g1|g)|g/|g4/(t/2)*3. |πA fundamental theorem 
  948  due to Minkowski (``Every |εt-|πdimensional convex 
  954  set symmetric about the origin with volume |ε|→|¬R2|gt 
  962  |πcontains a nonzero integer point'') gives |ε|≤m|βt|4|¬E|42
  968  |gt; |πthis is stronger than Hermite's theorem 
  975  for |εt|4|¬R|49. |πAnd even stronger results 
  981  are known, cf. (41).]|'{A3}|≡1|≡0|≡.|9|4|πSince 
  986  |εy|β1 |πand |εy|β2 |πare relatively prime, we 
  993  can solve |εu|β1y|β2|4α_↓|4u|β2y|β1|4α=↓|4m; 
  996  |πfurthermore (|εu|β1|4α+↓|4qy|β1)y|β2|4α_↓|4(u|β2|4α+↓|4qy|
  997  β2)y|β1|4α=↓|4m |πfor all |εq, |πso we can ensure 
 1005  that 2|¬G|εu|β1y|β1|4α+↓|4u|β2y|β2|¬G|4|¬E|4y|=|β1|g2|4α+↓|4
 1006  y|=|β2|g2 |πby choosing an appropriate integer 
 1012  |εq. |πNow |εy|β2(u|β1|4α+↓|4au|β2)|4|"o|4y|β2u|β1|4α_↓|4y|β
 1014  1u|β2|4|"o|40 (|πmodulo |εm), |πand |εy|β2 |πmust 
 1020  be relatively prime to |εm, |πhence |εu|β1|4α+↓|4au|β2|4|"o|
 1026  40. |πFinally let |¬G|εu|β1y|β1|4α+↓|4u|β2y|β2|¬G|4α=↓|4|≤am
 1029  , u|=|β1|g2|4α+↓|4u|=|β2|g2|4α=↓|4|≤bm, y|=|β1|g2|4α+↓|4y|=|
 1031  β2|g2|4α=↓|4|≤gm; |πwe have |ε0|4|¬E|4|≤a|4|¬E|4|f1|d32|)|≤g
 1034  . |πand it remains to be shown that |ε|≤a|4|¬E|4|f1|d32|)|≤b
 1042   |πand |ε|≤b|≤G|4|¬R|41. |πThe identity (|εu|β1y|β2|4α_↓|4u|
 1047  β2y|β1)|g2|4α+↓|4(u|β1y|β1|4α+↓|4u|β2y|β2)|g2|4α=↓|4(u|=|β1|
 1047  g2|4α+↓|4u|=|β2|g2)(y|=|β1|g2|4α+↓|4y|=|β2|g2) 
 1048  |πimplies that 1|4α+↓|4|≤a|g2|4α=↓|4|≤b|≤g. |πIf 
 1052  |ε|≤a|4|¬Q|4|f1|d32|)|≤b, |πwe have |ε2|≤a|≤g|4|¬Q|41|4α+↓|4
 1055  |≤a|g2, |πi.e., |ε|≤g|4α_↓|4{H11}|¬H{H9}|v4|≤g|g2|4α_↓|41|)|
 1057  4|¬W|4|≤a|4|¬E|4|f1|d32|)|≤g. |πBut |f1|d32|)|ε|≤g|4|¬W|4{H1
 1059  1}|¬H{H9}|v4|≤g|g2|4α_↓|41|) |πimplies that |ε|≤g|g2|4|¬Q|4|
 1062  f4|d33|), |πa contradiction.|'{A3}|≡1|≡1|≡.|9|πSince 
 1066  |εa |πis odd, |εy|β1|4α+↓|4y|β2 |πmust be even. 
 1073  To avoid solutions with |εy|β1 |πand |εy|β2 |πboth 
 1081  even, let |εy|β1|4α=↓|4x|β1|4α+↓|4x|β2, y|β2|4α=↓|4x|β1|4α_↓
 1084  |4x|β2, |πand solve |εx|=|β1|g2|4α+↓|4x|=|β2|g2|4α=↓|4|εm/{H
 1087  11}|¬H{H9}|v43|)|4α_↓|4|≤e, |πwith (|εx|β1,|4x|β2) 
 1090  |πrelatively prime and |εx|β1 |πeven; |πthe corresponding 
 1097  multiplier |εa |πwill be the solution to (|εx|β2|4α_↓|4x|β1)
 1104  a|4|"o|4x|β2|4α+↓|4x|β1 (|πmodulo 2|ε|ge). |πIt 
 1108  is not di∃cult to prove that |εa|4|"o|41 (|πmodulo 
 1116  2|ε|gk|gα+↓|g1) |πi= |εx|β1|4|"o|40 (|πmodulo 
 1120  |ε2|gk), |πso we get the best potency when |εx|β1 
 1129  |πmod 4|4α=↓|42. The problem reduces to _nding 
 1136  relatively prime solutions to |εx|=|β1|g2|4α+↓|4x|=|β2|g2|4α
 1140  =↓|4N |πwhere |εN |πis a large integer of the 
 1149  form |ε4k|4α+↓|41. |πBy factoring |εN |πover 
 1155  the Gaussian integers, we can see that solutions 
 1163  exist if and only if each prime factor of |εN 
 1173  (|πover the usual integers) has the form |ε\**k*?*?an 
 1181  integers, we can see that solutions exist if 
 1189  and only if each prime factor of |εN (|πover 
 1198  the usual integers) has the form |ε4k|4α+↓|41.|'
 1205  !!|2|πAccording to a famous theorem of Fermat, 
 1212  every prime |εp |πof the form |ε4k|4α+↓|41 |πcan 
 1220  be written |εp|4α=↓|4u|g2|4α+↓|4v|g2|4α=↓|4(u|4α+↓|4iv)(u|4α
 1222  _↓|4iv), v |πeven, in a unique way except for 
 1231  the signs of |εu |πand |εv. |πThe numbers |εu 
 1240  |πand |εv |πcan be calculated e∃ciently by solving 
 1248  |εx|g2|4|"o|4|→α_↓1 (|πmodulo |εp), |πthen calculating 
 1253  |εu|4α+↓|4iv|4α=↓|4|πgcd(|εx|4α+↓|4i,|4p) |πby 
 1255  Euclid's algorithm over the Gaussian integers. 
 1261  [We can take |εx|4α=↓|4n|g(|gp|gα_↓|g1|g)|g/|g4 
 1265  |πmod|6|εp |πfor almost half of all integers 
 1272  |εn. |πThis application of a Euclidean algorithm 
 1279  is essentially the same as _nding the least nonzero 
 1288  |εu|g2|4α+↓|4v|g2 |πsuch that |εu|4|¬N|4xv|4|"o|40 
 1292  (|πmodulo |εp)*3] |πIf the prime factorization 
 1298  of |εN |πis |εp|ure|β1|)1|)|4.|4.|4.|4p|ure|βr|)r|)|4α=↓|4(u
 1301  |β1|4α+↓|4iv|β1)|ge|r1 (u|β1|4α_↓|4iv|β1)|ge|r1|4.|4.|4.|4(u
 1302  |βr|4α+↓|4iv|βr)|ge|rr(u|βr|4α_↓|4iv|βr)|ge|rr, 
 1303  |πwe get |ε2|gr|gα_↓|g1 |πdistinct solutions 
 1308  to |εx|=|β1|g2|4α+↓|4x|=|β2|g2|4α=↓|4N, |πgcd(|εx|β1,|4x|β2)
 1310  |4α=↓|41, x|β1 |πeven, by letting |ε|¬Gx|β2|¬G|4α+↓|4i|¬Gx|β
 1315  1|¬G|4α=↓|4(u|β1|4α+↓|4iv|β1)|ge|r1(u|β2|4|¬N|4iv|β2)|ge|r2|
 1315  4.|4.|4. (u|βr|4|¬N|4iv|βr)|ge|rr; |πand all 
 1319  such solutions are obtained in this way.|'!!|2|εNote|*/: 
 1327  |\|εWhen |εm|4α=↓|410|ge, |πa similar procedure 
 1332  can be used, but it's _ve times as much work 
 1342  since we must keep trying until _nding a solution 
 1351  with |εx|β1|4|"o|40 (|πmodulo 10). For example, 
 1357  when |εm|4α=↓|410|g1|g0 |πwe have |"l|εm/{H11}|¬H{H9}|v43|)|
 1361  ¬L|4α=↓|4|π5773502691, and 5773502689|4α=↓|453|4|¬O|41089340
 1363  13|4α=↓|4(7|4α+↓|42|εi)(7|4α_↓|42i)(2203|4α+↓|410202i)(2203|
 1363  4α_↓|410202i). |πOf the two solutions |¬G|εx|β2|¬G|4α+↓|4i|¬
 1368  Gx|β1|¬G|4α=↓|4(7|4α+↓|42i)(2203|4α+↓|410202i) 
 1369  |πor (|ε7|4α+↓|42i)(2203|4α_↓|410202i), |πthe 
 1372  former gives |¬G|εx|β1|¬G|4α=↓|467008 (no good) 
 1377  and the latter gives |¬Gx|β1|¬G|4α=↓|475820, 
 1382  |¬G|εx|β2|¬G|4α=↓|4|π4983 (which is usable). 
 1386  Line 9 of Table |π1 was obtained by taking |εx|β1|4α=↓|47582
 1395  0, |εx|β2|4α=↓|4|→α_↓4983.|'!!|2|πLine 20 of 
 1400  the table was obtained as follows: |"l2|g3|g5/{H11}|¬H{H9}|v
 1406  43|)|¬L|4α=↓|419837604196; 19837604193 is divisible 
 1410  by 3 so it is ineligible; 19837604189 is divisible 
 1419  by 19, and 19837604185 by 7, and 19837604181 
 1427  by 3; 19837604177 is prime and equals 131884|g2|4α+↓|449439|
 1434  g2. The corresponding multiplier is 1175245817; 
 1440  a better one could be found if we continued searching. 
 1450  The multiplier on line 24 was obtained as the 
 1459  be{U0}{H9L11M29}W58320#Computer Programming|9(Knuth/Addison-
folio 693 galley 3
 1460  Wesley)|9f. 693|9Answers|9g. 3a|'{A6}|≡1|≡2|≡.|9|4|εU|=|βj|g
 1463  |¬S|4|¬O|4U|=|βj|g|¬Sα=↓U|βj|4|¬O|4|βjα+↓2|¬K|βi|βα=↓|βjq|βi
 1463  U|βi|4|¬O|4U|βj|4α+↓|4|¬K|βi|βα=↓|βj|¬K|βk|βα=↓|βjq|βiq|βkU|
 1463  βi|4|¬O|4U|βk. |πThe partial derivative with 
 1468  respect to |εq|βk |πis twice the left-hand side 
 1476  of (26). If the minimum can be achieved, these 
 1485  partial derivatives must all vanish.|'{A3}|≡1|≡3|≡.|9|4|εu|β
 1490  1|β1|4α=↓|41, u|β2|β1|4α=↓|4|πirrational, |εu|β1|β2|4α=↓|40.
 1492  |'{A3}|π|≡1|≡4|≡.|9|4After three uclidean steps 
 1497  we _nd |ε|≤n|=|β2|g2|4α=↓|45|g2|4α+↓|45|g2, |πthen 
 1501  S4 produces|'{A6}|εU|4α=↓|4|≥a|(|5|5|→α_↓5!|9|75!|9|7|d5|(|→
 1503  α_↓18!|→α_↓2!|9|70|q|d5!|4|41!|→α_↓2!|9|71|)|)|≥s,!!V|4α=↓|4
 1503  |≥a|(|→α_↓2!|618!|5|5|d5|(|→α_↓5!|→α_↓5!|4|→α_↓5|q|d5|9|70!|
 1503  9|70!100|)|)|≥s.|;{A6}|πTransformations (|εj,|4q|β1,|4q|β2,|
 1505  4q|β3)|4α=↓|4(1,|4|≤⊂,|40,|42), (2,|4|→α_↓4,|4|≤⊂,|41), 
 1507  (3,|40,|40,|4|≤⊂), (1,|4|≤⊂,|40,|40) |πresult 
 1510  in|'{A6}|εU|4α=↓|4|≥a|(|→α_↓3!|9|71!|9|72|d5|(|→α_↓5!|→α_↓8!
 1511  |→α_↓7|q|d5|9|71!|→α_↓2!|9|71|)|)|≥s,!!V|4α=↓|4|≥a|(|→α_↓22!
 1511  |5|5|→α_↓2!|618|d5|(|5|5|→α_↓5!|5|5|→α_↓5!|→α_↓5|q|d5!|4|49!
 1511  |→α_↓31!|629|)|)|≥s,!!Z|4α=↓|4(0!0!1).|;{A6}|πThus 
 1513  |ε|≤n|β3|4α=↓|4{H10}|¬H{H9}|v46|), |πas we already 
 1517  knew from exercise 3.|'{A3}|≡1|≡5|≡.|9|4The largest 
 1523  achievable |εq |πin (11), minus the smallest 
 1530  achievable, plus 1, is |¬G|εu|β1|¬G|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓
 1534  |4|¬Gu|βt|¬G|4α_↓|4|≤d, |πwhere |ε|≤d|4α=↓|41 
 1537  |πif |εu|βiu|βj|4|¬WQ|4*?*?*?vable, plus 1, is |¬G|εu|β1|¬G|4α+
 1542  ↓|4|¬O|4|¬O|4|¬O|4α+↓|4|¬Gu|βt|¬G|4α_↓|4|≤d, 
 1543  |πwhere |ε|≤d|4α=↓|41 |πif |εu|βiu|βj|4|¬W|40 
 1547  |πfor some |εi |πand |εj, |πotherwise |ε|≤d|4α=↓|40. 
 1554  |πFor example if |εt|4α=↓|45, u|β1|4|¬Q|40, u|β3|4|¬Q|40, 
 1560  u|β4|4α=↓|40, |πand |εu|β5|4|¬W|40, |πthe largest 
 1565  achievable value is |εq|4α=↓|4u|β1|4α+↓|4u|β2|4α+↓|4u|β3|4α_
 1568  ↓|41 |πand the smallest achievable is |εq|4α=↓|4u|β5|4α+↓|41
 1574  |4α=↓|4|→α_↓|¬Gu|β5|¬G|4α+↓|41.|'!|9[|πNote that 
 1577  the number of hyperplanes is unchanged when |εc 
 1585  |πvaries, hence the same answer applies to the 
 1593  problem of covering |εL |πinstead of |εL|β0. 
 1600  |πHowever, the stated formula is |εnot |πalways 
 1607  exact for covering |εL|β0, |πsince the hyperplanes 
 1614  which intersect the unit hypercube may not all 
 1622  contain points of |εL|β0. |πFor example, we can 
 1630  never achieve the value |εq|4α=↓|4u|β1|4α+↓|4u|β2|4α+↓|4u|β3
 1634  |4α_↓|41 |πin |εL|β0 |πif |εu|β1|4α+↓|4u|β2|4α+↓|4u|β3|4|¬Q|
 1638  4m; |πit is achievable i= there is a solution 
 1647  to |εm|4α_↓I4*?*?it is achievable i= there is a 
 1655  solution to |εm|4α_↓|4u|β1|4α_↓|4u|β2|4α_↓|4u|β3|4α=↓|4x|β1u
 1657  |β1|4α+↓|4x|β2u|β2|4α+↓|4x|β3u|β3|4α+↓|4x|β4|¬Gu|β5|¬G 
 1658  |πin nonnegative integers (|εx|β1,|4x|β2,|4x|β3,|4x|β4). 
 1662  |πIt may be true that the stated limits are always 
 1672  achievable when |¬Gu|β1|¬G|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|¬Gu|βt|¬
 1674  G |πis minimal, but this does not appear to be 
 1684  obvious.]|'{A3}|≡1|≡6|≡.|9|4It su∃ces to determine 
 1689  all solutions to (15) having minimum |¬G|εu|β1|¬G|4α+↓|4|¬O|
 1695  4|¬O|4|¬O|4α~∩↓4|¬Gu|βt|¬G, |πsubtracting 1 if 
 1699  any one of these solutions has components of 
 1707  opposite sign.|'!|9Instead of posuppi*?*?*?*?ng 1 
 1713  if any one of these solutions has components 
 1721  of opposite sign.|'!|9Instead of positive de_nite 
 1728  quadratic forms, we work with |εf|1(x|β1,|4.|4.|4.|4,|4x|βt)
 1733  |4α=↓|4|¬Gx|β1U|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4x|βtU|βt|¬G, 
 1734  |πde_ning |¬G|εY|¬G|4α=↓|4|¬Gy|β1|¬G|4α+↓|4|¬O|4|¬O|4|¬O|4α+
 1735  ↓|4|¬Gy|βt|¬G. |πInequality (21) can be replaced 
 1741  by |¬G|εx|βk|¬G|4|¬E|4(|πmax|ε|β1|β|¬E|βj|β|¬E|βt|2|¬Gv|βk|β
 1742  j|¬G)|1f|1(y|β1,|4.|4.|4.|4,|4y|βt).|'!|9|πThus 
 1744  a workable algorithm can be obtained as follows. 
 1752  Replace steps S1 through S3 by: ``Set |εU|5|¬L|5(m), 
 1760  V|5|¬L|5(1), r|5|¬L|51, s|5|¬L|5m, t|5|¬L|51.'' 
 1764  (Here |εU |πand |εV |πare 1|4α⊗↓|41 matrices; 
 1771  thus the two-dimensional case will be handled 
 1778  by the general method. A special procedure for 
 1786  |εt|4α=↓|42 |πcould, of course, be devised.) 
 1792  In steps S4 and S8, set |εs|5|¬L|5|πmin(|εs,|4|¬GU|βk|¬G), 
 1799  |πIn step S8, set |εz|βk|5|¬L|5|"l|πmax|ε|β1|β|¬E|βj|β|¬E|βt
 1803  |¬Gv|βk|βj|¬Gs/m|¬L. |πIn step S10, set |εs|5|¬L|5|πmin(|εs,
 1808  |4|¬GY|¬G|4α_↓|4|≤d); |πand in step S11, output 
 1814  |εs|4α=↓|4N|βt. |πOtherwise leave the algorithm 
 1819  as it stands, since it already produces suitably 
 1827  short vectors. [|εMath. Comp. |π|≡2|≡9 (1975), 
 1833  827<833.]|'{A3}|≡1|≡7|≡.|9|4When |εk|4|¬Q|4t 
 1836  |πin S10, and if |εY|4|¬O|4Y|4|¬E|4s, |πoutput 
 1842  |εY (|πand also |ε|→α_↓Y, |πif desired for completeness); 
 1850  if |εY|4|¬O|4Y|4|¬W|4s, |πtake back the previous 
 1856  output of vectors for this |εt. [|πIn the author's 
 1865  experience preparing Table 1, there was exactly 
 1872  one vekctttt |εY|4|¬O|4Y|4|¬E|4s, |πoutput |εY 
 1877  (|πand also |ε|→α_↓Y, |πif desired for completeness); 
 1884  if |εY|4|¬O|4Y|4|¬W|4s, |πtake back the previous 
 1890  output of vectors for this |εt. [|πIn the author's 
 1899  experience preparing Table 1, there was exactly 
 1906  one vector output for each |ε|≤n|βt, |πexcept 
 1913  when |εy|β1|4α=↓|40 |πor |εy|βt|4α=↓|40.]|'|≡1|≡8|≡.|9|4a) 
 1918  |πLet |εx|4α=↓|4m, y|4α=↓|4(1|4α_↓|4m)/3, v|βi|βj|4α=↓|4y|4α
 1921  +↓|4x|≤d|βi|βj, u|βi|βj|4α=↓|4|→α_↓y|4α+↓|4|≤d|βi|βj. 
 1923  |πThen |εV|βj|4|¬O|4V|βk|4α=↓|4|f1|d33|)(m|g2|4α_↓|41) 
 1925  |πfor |εj|4|=|↔6α=↓|4k, |εV|βk|4|¬O|4V|βk|4α=↓|4|f2|d33|)(m|
 1927  g2|4α+↓|4|f1|d32|)), U|βj|4|¬O|4U|βj|4α=↓|4|f1|d33|)(m|g2|4α
 1928  +↓|42), |εz|βk|4|¬x|4{H10}|¬H{H9}|v4|f2|d39|)|)|4m. 
 1930  (|πThis example satis_es (28) with |εa|4α=↓|41 
 1936  and works for all |εm|4|≠-|41 (|πmodulo 3).)|'
 1943  !!|2|πb) Interchange the roll!!|2|πb) Interchange 
 1948  the roles of |εU |πand |εV |πin step S5. Also 
 1958  set |εs|5|¬L|5|πmin(|εs,|4U|βi|4|¬O|4U|βi) |πfor 
 1961  all |εU|βi |πthat change. For example, when |εm|4α=↓|464 
 1969  |πthis transformation with |εj|4α=↓|41, |πapplied 
 1974  to the matrices of (a), reduces|'{A9}{M36}|εV|4α=↓|4|≥a|(|9|
 1980  743!|→α_↓21!|→α_↓21|d5|(|→α_↓21!!|9|743!|→α_↓21|q|d5|→α_↓21!
 1980  |→α_↓21!|9|7|)|)|≥s,!U|4α=↓|4|≥a|(22!21!21|d5|(21!22!21|q|d5
 1980  21!21!22|)|)|≥s!!|πto!!|εV|4α=↓|4|≥a|(!|4|41!!|4|41!!|4|41|d
 1980  5|(|→α_↓21!|9|743!|→α_↓21|q|d5|→α_↓21!|→α_↓21!|9|743|)|)|≥s,
 1980  !U|4α=↓|4|≥a|(|622!21!21|d5|(|→α_↓1!|5|51!|5|5|q|d5|→α_↓1!|5
 1980  |50!|5|51|)|)|≥s.|'{A9}{M29}[|πSince the transformation 
 1984  can increase the length of |εV|βj, |πan algorithm 
 1992  which incorporates both transformations must 
 1997  be careful to avoid in_nite looping.]|'{A3}|≡1|≡9|≡.|9|4No, 
 2004  since a product of non-identity matrices with 
 2011  all o=-diagonal elements nonnegative and all 
 2017  diagonal elements 1 cannot be the identity. [However, 
 2025  looping would be possible if a subsequent transformation 
 2033  with |εq|4α=↓|4|→α_↓1 |πwere performed when |ε|→α_↓2V|βi|4|¬
 2038  O|4V|βj|4α=↓|4V|βj|4|¬O|4V|βj; |πthe rounding 
 2041  rule must be asymmetric with respect to sign 
 2049  if non-shortening transformations are allowed.]|'
 2054  {A3}|≡2|≡0|≡.|9|4Use the ordinary spectral test 
 2059  for |εa |πand |εm|4α=↓|42|ge|gα_↓|g2; |πvkf.*?*?pect 
 2064  to sign if non-shortening transformations are 
 2070  allowed.]|'{A3}|≡2|≡0|≡.|9|4Use the ordinary 
 2074  spectral test for |εa |πand |εm|4α=↓|42|ge|gα_↓|g2; 
 2080  |πcf. exercise 3.2.1.2<9. [On intuitive grounds, 
 2086  the same answer should apply also when |εa |πmod 
 2095  8|4α=↓|43.]|'{A3}|≡2|≡1|≡.|9|4|εX|β4|βn|βα+↓|β4|4|≠-|4X|β4|β
 2096  n (|πmodulo 4), so it is appropriate to let |εV|β1|4α=↓|4(4,
 2105  |44a|g2,|44a|g3)/m, |εV|β2|4α=↓|4(0,|41,|40), 
 2107  V|β3|4α=↓|4(0,|40,|41) de_ne the corresponding 
 2111  lattice |εL|β0.|'{A3}|≡2|≡4|≡.|9|4|πLet |εm|4α=↓|4p; 
 2115  |πan analysis paralleling the text can be given. 
 2123  For example, when |εt|4α=↓|44 |πwe have |εX|βn|βα+↓|β3|4α=↓|
 2129  4{H11}({H9}(a|g2|4α+↓|4b)X|βn|βα+↓|β1|4α+↓|4abX|βn{H11}){H9}
 2129  |πmod|4|εn, |πand we want to minimize |εu|=|β1|g2|4α+↓|4u|=|
 2135  β2|g2|4α+↓|4u|=|β3|g2|4α+↓|4u|=|β4|g2|4|=|↔6α=↓|40 
 2136  |πsuch that |εu|β1|4α+↓|4bu|β3|4α+↓|4abu|β4|"o|4u|β2|4α+↓|4a
 2138  u|β3|4α+↓|4(a|g2|4α+↓|4b)u|β4|4|"o|40 (|πmodulo 
 2140  |εm).|'!|9|πReplace steps S1 through S3 by the 
 2148  operations of setting|'{A6}|εU|4|"L|5|↔a|(m|d50|)!|(0|d5m|)|
 2151  ↔s,!!V|5|¬L|5|↔a|(1!0|d50!1|)|↔s,!!R|5|¬L|5|↔a|(1!0|d50!1|)|
 2151  ↔s,!!s|5|¬L|5m|g2,!!t|5|¬L|52,|;{A9}|πand outputting 
 2154  |ε|≤n|β2|4α=↓|4m. |πReplace step S4 by|'{A3}{I1.7L}{I1.7H}|π
 2159  |≡S|≡4|¬S|≡.|9[Advance |εt.] |πIf |εt|4α=↓|4T, 
 2163  |πthe algorithm terminates. Otherwise set |εt|5|¬L|5t|4α+↓|4
 2168  1 |πand |εR|5|¬L|5R(|f0|d51|)!|fb|d5a|))|πmod|4|εm. 
 2171  |πSet |εU|βt |πto the new row (|→α_↓|εr|β1|β2,|4|→α_↓r|β2|β2
 2177  ,|40,|4.|4.|4.|4,|40,|41) |πof |εt |πelements, 
 2181  and set |εu|βi|βt|5|¬L|50 |πfor |ε1|4|¬E|4i|4|¬W|4t. 
 2186  |πSet |εV|βt |πto the new row (0,|4.|4.|4.|4,|40,|4|εm). 
 2193  |πFor |ε1|4|¬E|4|εi|4|¬W|4t, |πset |εq|5|¬L|5|πround{H11}({H
 2196  9}(|εv|βi|β1r|β1|β2|4α+↓|4v|βi|β2r|β2|β2)/m{H11}){H9}, 
 2197  v|βi|βt|5|¬L|5v|βi|β1r|β1|β2|4α+↓|4v|βi|β2r|β2|β2|4α_↓|4qm, 
 2198  |πand |εU|βt|5|¬L|5U|βt|4α+↓|4qU|βi. |πFinally 
 2201  set |εs|5|¬L|5|πmin(|εs,|4U|βt|4|¬O|4U|βt), k|5|¬L|5t, 
 2204  j|5|¬L|51.|'!!!!|4[|πA similar generalization 
 2208  applies to all sequences of length |εp|gk{U0}{H10L12M29}W583
folio 701 galley 4
 2214  20#Computer Programming|9(knuth/Addison-Wesley)|9f. 
 2216  701|9Answers|9g. 4a|'{A6}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|4|4|∨3|∨.|∨4|
 2218  ∨.|∨1|'{A12}{H9L11}|5|5|≡1|≡.|9|4|ε|≤a|4α+↓|4(|≤b|4α_↓|4|≤a)
 2219  U.|'{A3}|5|5|≡2|≡.|9|4|πLet |εU|4α=↓|4X/m; |"lkU|"L|4α=↓|4r 
 2223  |πif and only if |εr|4|¬E|4kX/m|4|¬W|4r|4α+↓|41, 
 2228  |πthat is |εmr/k|4|¬E|4X|4|¬W|4m(r|4α+↓|41)/k, 
 2231  |πthat is |"pmr/k|"P|4|¬E|4X|4|¬W|4|"pm(r|4α+↓|41)/k|"P. 
 2234  |πThe exact probability is (|ε1/m)(|"pm(r|4α+↓|41)/k|"P|4α_↓
 2238  |4|"pmr/k|"P{H11}){H9}|4α=↓|41/k|4α+↓|4|≤e, |¬G|≤e|¬G|4|¬W|4
 2239  1/m.|'{A3}|5|5|≡3|≡.|9|4|πIf full-word random 
 2243  numbers are given, the result will be su∃ciently 
 2251  random as in exercise 2. But if a linear congruential 
 2261  sequence is used, |εk |πmust be relatively prime 
 2269  to the modulus |εm, |πlest the numbers have a 
 2278  very short period (e.g., if |εk|4α=↓|42 |πand 
 2285  |εm |πis even, the numbers will at best be alternately 
 2295  0 and 1), by the results of Section 3.2.1.1. 
 2304  The method is slower than (1) in nearly every 
 2313  case, so it is not recommended.|'{A3}|5|5|≡4|≡.|9|4max(|εX|β
 2319  1,|4X|β2)|4|¬E|4x |πif and only if |εX|β1|4|¬E|4x 
 2325  |πand |εX|β2|4|¬E|4x; |πmin(|εX|β1,|4X|β2)|4|¬R|4x 
 2328  |πif and only if |εX|β1|4|¬R|4x |πand |εX|β2|4|¬R|4x. 
 2335  |πThe probability that two independent events 
 2341  both happen is the product of the individual 
 2349  probabilities.|'|5|5|≡5|≡.|9|4|πObtain independent 
 2352  uniform deviates |εU|β1, U|β2. |πSet |εX|4|¬L|4U|β2. 
 2358  |πIf |εU|β1|4|¬R|4p, |πset |εX|4|¬L|4|πmax(|εX,|4U|β3), 
 2362  |πwhere |εU|β3 |πis a third uniform deviate. 
 2369  If |εU|β1|4|¬R|4p|4α+↓|4q, |πalso set |εX|5|¬L|5|πmax(|εX,|4
 2373  U|β4), |πwhere |εU|β4 |πis a fourth uniform deviate. 
 2381  This method can obviously be generalized to any 
 2389  polynomial, and indeed even to in_nite power 
 2396  series (as shown for example in Algorithm S, 
 2404  which uses minimization instead of maximization).|'
 2410  !!|2Alternatively, we could proceed as follows 
 2416  (suggested by M. D. MacLaren): If |εU|β1|4|¬W|4p, 
 2423  |πset |εX|5|¬L|5U|β1/p; |πotherwise if |εU|β1|4|¬W|4p|4α+↓|4
 2427  q, |πset |εX|5|¬L|5|πmax{H11}({H9}(|εU|β1|4α_↓|4p)/q,|4U|ε|β
 2429  2{H11}){H9}; |πotherwise set |εX|5|¬L|5|πmax{H11}({H9}(|εU|β
 2432  1|4α_↓|4p|4α_↓|4q)/r, U|β2,|4U|β3{H11}){H9}. 
 2434  |π|πThis method requires less time than the other 
 2442  to obtain the uniform deviates, although it involves 
 2450  further arithmetical operations and it is less 
 2457  stable numerically.|'{A6}|5|5|≡6|≡.|9|4|εF(x)|4α=↓|4A|β1/(A|
 2459  β1|4α+↓|4A|β2), |πwhere |εA|β1 |πand |εA|β2 |πare 
 2465  the areas in Fig. A-4; so|'{A6}{M29}|εF(x)|4α=↓|4|(|¬J|urx|)
 2471  0|)|4{H10}|¬H{H9}|v21|4α_↓|4y|g2|)|4dy|d2|¬J|ur1|)0|)|4{H10}
 2471  |¬H{H9}|v21|4α_↓|4y|g2|)|4dy|)|4α=↓|4|(2|d2|≤p|)|4|πarcsin|4
 2471  |εx|4α+↓|4|(2|d2|≤p|)|4x|2{H10}|¬H{H9}|v21|4α_↓|4x|g2|).|'
 2472  {A6}|πThe probability of termination at step 
 2478  2 is |εp|4α=↓|4|≤p/4, |πeach time step 2 is encountered, 
 2487  so the number of executions of step 2 has the 
 2497  geometric distribution. The characteristics of 
 2502  this number are (min|41, ave|44/|ε|≤p, |πmax|4|¬X, 
 2508  dev|4(|ε4/|≤p)|2{H10}|¬H{H9}|v41|4α_↓|4|≤p/4|)), 
 2509  |πby exercise 17.|'{A6}|≡F|≡i|≡g|≡.|4|4|≡A|≡<|≡4|≡.|9|4|πReg
 2512  ion of ``acceptance'' for the algorithm of exercise 
 2520  6.|;{A6}|5|5|≡7|≡.|9|4The altitude of |εp|βjf|βj(x) 
 2525  |πmust not exceed |εf|1(x), |πsince each component 
 2532  |εf|βk(x) |πof Eq. (14) must be |→|¬R0. Now |εp|βj 
 2541  |πis the area under the curve |εp|βjf|βj(x), 
 2548  |πthat is, the altitude of |εp|βjf|βj(x) |πtimes 
 2555  |f1|d34|). So the given value is the largest 
 2563  multiple of |f1|d3256|) which satis_es the conditions.{A3}|5
 2569  |5|≡8|≡.|9|4The idea is to make the selection 
 2576  of the large rectangle distributions as e∃cient 
 2583  as possible. (An analogous situation is given 
 2590  in exercise 21.)|'{A3}|5|5|≡9|≡.|9|4Consider 
 2594  the sign of |εf|1|¬P(x)|4α=↓|4{H10}|¬H{H9}|v42/|≤p|)|1(x|g2|
 2597  4α_↓|41)e|gα_↓|gx|i2|g/|g2.|'{A3}|≡1|≡0|≡.|9|4|πFigure 
 2599  10 shows how |εa|βj |πand |εb|βj |πmust be chosen 
 2608  for the cases that |εf|1(x) |πis concave |πup 
 2616  or down. Letting |εs|βj|4α=↓|4|f1|d34|)(j|4α_↓|41) 
 2620  |πand |εh|4α=↓|4|f1|d34|), |πwe _nd that|'{A9}|εf|βj|βα+↓|β2
 2625  |β4(x)|4|∂α=↓|4|(1|d2p|βj|βα+↓|β2|β4|)|4|↔H|(2|d2|≤p|)|4(e|g
 2625  α_↓|gx|i2|g/|g2|4α_↓|4e|gα_↓|g(|gj|g/|g4|g)|i2|g/|g2),!!s|βj
 2625  |4|¬E|4x|4|¬E|4s|βj|4α+↓|4h;|'{A4}| p|βj|βα+↓|β2|β4|4|L|4|↔H
 2626  |(2|d2|≤p|)|4|↔j|urs|βjα+↓1/4|)s|βj|)|4(e|gα_↓|gt|i2|g/|g2|4
 2626  α_↓|4e|gα_↓|g(|gj|g/|g4|g)|i2|g/|g2)|4dt>{A4}| a|βj|4|L|4f|β
 2627  j|βα+↓|β2|β4(s|βj),!!b|βj|4α=↓|4|→α_↓hf|=|βj|¬S|βα+↓|β2|β4(s
 2627  |βj|4α+↓|4h),!!|πfor|4|41|4|¬E|4j|4|¬E|44;>{A4}| |εa|βj|4|Lα
 2628  =↓|4f|βj|βα+↓|β2|β4(x|βj)|4α+↓|4(x|βj|4α_↓|4s|βj)b|βj/h,!!b|
 2628  βj|4α=↓|4f|βj|βα+↓|β2|β4(s|βj),!!|πfor|4|4|ε5|4|¬E|4j|4|¬E|4
 2628  12,>{A9}|πwhere |εx|βj |πis the root of the equation 
 2637  |εf|=|βj|¬S|βα+↓|β2|β4(x|βj)|4α=↓|4|→α_↓b|βj/h. 
 2638  |πNote that in Eqs. (20) we have |εE[j]|4α=↓|416/j, 
 2646  |πfor |ε1|4|¬E|4j|4|¬E|44; |εE[j]|4α=↓|41/(e|gj|g/|g1|g6|gα_
 2648  ↓|g1|g/|g3|g2|4α_↓|41), |πfor |ε5|4|¬E|4j|4|¬E|412.|'
 2651  {A3}|≡1|≡1|≡.|9|4|πLet |εg(t)|4α=↓|4e|g9|g/|g2te|gα_↓|gt|i2|
 2652  g/|g2 |πfor |εt|4|¬R|43. |πSince |εG(x)|4α=↓|4|¬J|urx|)0|)|4
 2656  g(t)|4dt|4α=↓|41|4α_↓|4e|gα_↓|g(|gx|i2|gα_↓|g9|g)|g/|g2, 
 2657  |πa random variable |εX |πwith density |εg |πcan 
 2665  be computed by setting |εX|5|¬L|5G|gα_↓|g1(1|4α_↓|4V)|4α=↓|4
 2669  {H10}|¬H{H9}|v49|4α_↓|42|4|πln|4|εV|). |πNow 
 2671  |εe|gα_↓|gt|i2|g/|g2|4|¬E|4(t/3)e|gα_↓|gt|i2|g/|g2 
 2672  |πfor |εt|4|¬R|43, |πso we obtain a valid refection 
 2680  method if we accept |εX |πwith probability |εf|1(X)/cg(X)|4α
 2687  =↓|43/X.|'{A3}|≡1|≡2|≡.|9|4|πWe have |εf|¬S(x)|4α=↓|4xf|1(x)
 2690  |4α_↓|41|4|¬W|40 |πfor |εx|4|¬R|40, |πsince |εf|1(x)|4α=↓|4x
 2694  |gα_↓|g1|4α_↓|4e|gx|i2|g/|g2|3|¬J|ur|¬X|)x|)|3e|gα_↓|gt|i2|g
 2694  /|g2|4dt/t|g2 |πfor |εx|4|¬Q|40. |πLet |εx|4α=↓|4a|βj|βα_↓|β
 2698  1 |πand |εy|g2|4α=↓|4x|g2|4α+↓|42|4|πln|42; |πthen 
 2702  {H10}|¬H{H9}|v42/|≤p|)|3|¬J|ur|¬X|)|εy|)|3e|gα_↓|gt|i2|g/|g2
 2702  |4dt|4α=↓|4|f1|d32|)|2{H10}|¬H{H9}|v42/|≤p|)|4e|gα_↓|gx|i2|g
 2702  /|g2|1f|1(y)|4|¬W|4|f1|d32|)|2{H10}|¬H{H9}|v42/|≤p|)|4e|gα_↓
 2702  |gx|i2|g/|g2|1f|1(x)|4α=↓|42|gα_↓|gj, |πhence 
 2704  |εy|4|¬Q|4a|βj.|'{A3}|≡1|≡3|≡.|9|4take |εb|βj|4α=↓|4|≤m|βj; 
 2707  |πconsider now the problem with |ε|≤m|βj|4α=↓|40 
 2713  |πfor each |εj. |πIn matrix notation, if |εY|4α=↓|4AX, 
 2721  |πwhere |εA|4α=↓|4(a|βi|βj), |πwe need |εAA|gT|4α=↓|4C|4α=↓|
 2725  4(c|βi|βj). [|πIn other notation, if |εY|βj|4α=↓|4|¬K|4a|βj|
 2730  βkX|βk, |πthen the average value of |εY|βiY|βj 
 2737  |πis |¬K|4|εa|βi|βka|βj|βk.] |πIf this matrix 
 2742  equation can be solved for |εA, |πit can be solved 
 2752  when |εA |πis triangular, since |εA|4α=↓|4BU 
 2758  |πfor some orthogonal matrix |εU |πand some triangular 
 2766  |εB, |πand |εBB|gT|4α=↓|4C. |πThe desired triangular 
 2772  solution can be obtained by solving the equations 
 2780  |εa|=|β1|g2|β1|4α=↓|4c|β1|β1, a|β1|β1a|β2|β1|4α=↓|4c|β1|β2, 
 2782  a|=|β2|g2|β1|4α+↓|4a|=|β2|g2|β2|4α=↓|4c|β2|β2, 
 2783  a|β1|β1a|β3|β1|4α=↓|4c|β1|β3, a|β2|β1a|β3|β1|4α+↓|4a|β2|β2a|
 2784  β3|β2|4α=↓|4c|β2|β3,|4.|4.|4.|4,|4 |πsuccessively 
 2786  for |εa|β1|β1, a|β2|β1, a|β2|β2, a|β3|β1, a|β3|β2, 
 2792  |πetc. [|εNote|*/: |\|πThe covariance matrix must 
 2798  be positive semide_ne, since the average value 
 2805  of (|¬K|4|ε|βy|βjY|βj)|g2 |πis |¬K|4c|βi|βjy|βiy|βj, 
 2809  |πwhich must be nonnegative. And there is always 
 2817  a solution when |εC |πis positive semide_nite, 
 2824  since |εC|4α=↓|4U|gα_↓|g1|4|πdiag(|ε|≤l|β1,|4.|4.|4.|4,|4|≤l
 2825  |βn)U, |πwhere the eigenvalues |ε|≤l|βj |πare 
 2831  nonnegative, and |εU|gα_↓|g1|4|πdiag({H10}|¬H{H9}|v4|ε|≤l|β1
 2833  |),|4.|4.|4.|4,|4{H10}|¬H{H9}|v4|≤l|βn|))U |πis 
 2835  a solution.]|'{A3}|≡1|≡4|≡.|9|4|εF(x/c) |πif 
 2839  |εc|4|¬Q|40, |πa step function if |εc|4α=↓|40, 
 2845  |πand |ε1|4α_↓|4F(x/c) |πif |εc|4|¬W|40.|'{A3}|≡1|≡5|≡.|9|4|
 2849  πDistribution |¬J|ur|¬X|)α_↓|¬X|)|4|εF|β1(x|4α_↓|4t)|4dF|β2(
 2850  t). |πDensity |ε|¬J|ur|¬X|)α_↓|¬X|)|4f|β1(x|4α_↓|4t)|1f|β2(t
 2852  )|4dt. |πThis is called the |εconvolution |πof 
 2859  the given distributions.|'|Ha*?*?{U0}{H9L11M29}W58320#Computer
folio 707 galley 5
 2862   Programming|9(Knuth/Addison-Wesley)|9f. 707|9Answers|9g. 
 2865  5a|'{A6}|≡1|≡6|≡.|9|4|πIt is clear that |εf|1(t)|4|¬E|4cg(t)
 2870   |πfor all |εt |πas required. Since |¬J|ur|¬X|)0|)|4g(t)|4dt
 2877  |4α=↓|41 |πwe have |εg(t)|4α=↓|4Ct|g9|gα_↓|g1 
 2881  |πfor |ε0|4|¬E|4t|4|¬W|41, |εCe|gα_↓|gt |πfor 
 2885  |εt|4|¬R|41, |πwhere |εC|4α=↓|4|εae/(a|4α+↓|4e). 
 2888  |πA random variable with density |εg |πis easy 
 2896  to obtain as a mixture of two distributions, 
 2904  |εG|β1(x)|4α=↓|4x|g1|g/|ga |πfor |ε0|4|¬E|4x|4|¬W|41, 
 2907  |πand |εG|β2(x)|4α=↓|41|4α_↓|4|εe|g1|gα_↓|gx 
 2909  |πfor |εx|4|¬R|41:|'{A3}{I3.1H}|π!!|2|≡G|≡1|≡.|9[Initialize.
 2911  ] Set |εp|5|¬L|5e/(a|4α+↓|4e). (|πThis is the 
 2917  probability that |εG|β1 |πshould be used.)|'{A3}!!|2|≡G|≡2|≡
 2923  .|9[Generate |εG |πdeviate.] Generate independent 
 2928  uniform deviates |εU, V, |πwhere |εV|4|=|↔6α=↓|40. 
 2934  |πIf |εU|4|¬W|4p, |πset |εX|5|¬L|5V|g1|g/|ga 
 2938  |πand |εq|5|¬L|5e|gα_↓|gX; |πotherwise set |εX|5|¬L|51|4α_↓|
 2942  4|πln|4|εV |πand |εq|5|¬L|5X|ga|gα_↓|g1. (|πNow 
 2946  |εX |πhas density |εg, |πand |εq|4α=↓|4f|1(X)/cg(X).{H11})|'
 2952  {A3}{H9}|π!!|2|≡G|≡3|≡.|9[Reject?] Generate a 
 2955  new uniform deviate |εU. |πIf |εU|4|¬R|4q, |πreturn 
 2962  to G2.|'{A3}{IC}The average number of iterations 
 2969  is |ε1/c|4α=↓|4(a|4α+↓|4e)/e|≤)(a|4α+↓|41)|4|¬W|41.4.|'
 2971  !|9|πIt is possible to streamline this procedure 
 2978  in several ways. First, we can replace |εV |πby 
 2987  an exponential deviate |εY |πof mean 1, generated 
 2995  by Algorithm S, say, and then we set |εX|5|¬L|5e|gα_↓|gY|g/|
 3003  ga |πor |εX|5|¬L|51|5α+↓|5Y |πin the two cases. 
 3010  Moreover, if we set |εq|5|¬L|5pe|gα_↓|gX |πin 
 3016  the _rst case and |εq|5|¬L|5|εp|4α+↓|4(1|4α_↓|4p)X|ga|gα_↓|g
 3020  1 |πin the second, we can use the original |εU 
 3030  |πinstead of a newly generated one in step G3. 
 3039  Finally if |εU|4|¬W|4p/e |πwe can accept |εV|g1|g/|ga 
 3046  |πimmediately, avoiding the calculation of |εq 
 3052  |πabout 30 percent of the time.|'{A3}|≡1|≡7|≡.|9|4|π(a) 
 3059  |εF(x)|4α=↓|41|4α_↓|4(1|4α_↓|4p)|g|¬G|gx|g|¬G, 
 3060  |πfor |εx|4|¬R|40. |π(b) |εG(z)|4α=↓|4pz/{H11}({H9}1|4α_↓|4(
 3063  1|4α_↓|4p)z{H11}){H9}. (c) |πMean |ε1/p, |πstandard 
 3068  deviation {H10}|¬H{H9}|v41|4|εp/p. |πTo do the 
 3073  latter calculation, observe that if |εH(z)|4α=↓|4q|4α+↓|4(1|
 3078  4α_↓|4q)z, |πthen |εH|¬S(1)|4α=↓|41|4α_↓|4q |πand 
 3082  |εH|¬C(1)|4α+↓|4H|¬S(1)|4α_↓|4{H11}({H9}H|¬S(1){H11}){H9}|g2
 3082  |4α=↓|4q(1|4α_↓|4q), |πso the mean and variance 
 3088  of |ε1/H(z) |πare |εq|4α_↓|41 |πand |εq(q|4α_↓|41), 
 3094  |πrespectively. (See Section 1.2.10.) In this 
 3100  case, |εq|4α=↓|41/p; |πthe extra factor |εz |πin 
 3107  the numerator of |εG(z) |πincreases the mean 
 3114  by one.|'|≡1|≡8|≡.|9|4|πSet |εN|5|¬L|5N|β1|4α+↓|4N|β2|4α_↓|4
 3117  1, |πwhere |εN|β1 |πand |εN|β2 |πindependently 
 3123  have the geometric distribution for probability 
 3129  |εp. (|πConsider the generating function.)|'{A3}|≡1|≡9|≡.|9|
 3134  4Set |εN|5|¬L|5N|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4N|βt|4α_↓|4t, 
 3136  |πwhere the |εN|βj |πhave the geometric distribution 
 3143  for |εp. (|πThis is the number of failures before 
 3152  the |εt|πth success, when a sequence of independent 
 3160  trials are made each of which succeeds with probability 
 3169  |εp.)|'!!|2|πFor |εt|4α=↓|4p|4α=↓|4|f1|d32|), 
 3172  |πand in general when the mean value {H11}({H9}|πnamely 
 3180  |εt(1|4α_↓|4p)/p{H11}) {H9}|πof the distribution 
 3184  is small, we simply can evaluate the probabilities 
 3192  |εp|βn |4α=↓|4(|ft|4α_↓|41|4α+↓|4n|d5n|))p|gt(1|4α_↓|4p)|gn 
 3194  |πconsecutively for |εn|4α=↓|40,|41,|42,|4.|4.|4. 
 3197  |πas in the following algorithm:|'{A3}{I3.1H}!!|2|≡B|≡1|≡.|9
 3202  [Initialize.] Set |εN|5|¬L|50, q|5|¬L|5p|gt, 
 3206  r|5|¬L|5q, |πand generate a random uniform deviate 
 3213  |εU. (|πWe will have |εq|4α=↓|4p|βN |πand |εr|4α=↓|4p|β0|4α+
 3219  ↓|4|¬O|4|¬O|4|¬O|4α+↓|4p|βN |πduring this algorithm, 
 3223  which stops as soon as |εU|4|¬W|4r.)|'{A3}!!|2|≡B|≡2|≡.|9[Se
 3229  arch.] |πIf |εU|4|¬R|4r, |πset |εN|5|¬L|5N|4α+↓|41, 
 3234  q|5|¬L|5q(1|4α_↓|4p)(t|4α_↓|41|4α+↓|4N)/N, r|5|¬L|5r|4α+↓|4q
 3235  , |πand repeat this step.|'{A3}{IC}!!|2[An interesting 
 3242  technique for the negative binomial distribution, 
 3248  for arbitrarily large real values of |εt, |πhas 
 3256  been suggested by R. L|=1eger: First generate 
 3263  a random gamma deviate of order |εt, |πthen let 
 3272  |εN |πbe a random Poisson deviate of mean |εX(1|4α_↓|4p)/p.]
 3280  |'{A3}|≡2|≡0|≡.|9|4|πIf |ε0|4|¬E|4|εb|β1b|β2b|β3|4|¬W|46, 
 3283  |πset |εX|5|¬L|5|εA[b|β1b|β2b|β3]; |πif 48|4|¬E|4|εb|β1b|β2b
 3286  |β3b|β4b|β5b|β6|4|¬W|463, |πset |εX|5|¬L|5|εB[b|β1b|β2b|β3b|
 3288  β4b|β5b|β6]; |πotherwise set |εX|5|¬L|6|εC[b|β1b|β2b|β3b|β4b
 3291  |β5b|β6b|β7b|β8b|β9]. |πHere (|εA[0],|4.|4.|4.|4,|4|εA[5])|4
 3293  α=↓|4(x|β1,|4x|β2,|4x|β3,|4x|β3,|4x|β6,|4x|β6); 
 3294  (|εB[48],|4.|4.|4.|4,|4B[62])|4α=↓|4(|εx|β1, 
 3295  x|β1, x|β1, x|β2, x|β2, x|β4, x|β5, x|β5, x|β5, 
 3303  x|β6, x|β6, x|β6, x|β6, x|β6); (C[504],|4.|4.|4.|4,|4C[511])
 3308  |4α=↓|4(x|β1, x|β1, x|β2, x|β3, x|β3, x|β3, x|β4, 
 3315  x|β4).|'!!|2|πThis method uses 29 auxiliary table 
 3322  entries, which can be overlapped so that only 
 3330  21 are actually required: Let (|εD[0],|4.|4.|4.|4,|4D[20])|4
 3335  α=↓|4(x|β1, x|β1, x|β2, x|β4, x|β5, x|β5, x|β5, 
 3342  x|β5, x|β6, x|β6, x|β6, x|β6, x|β6, x|β2, x|β1, 
 3350  x|β3, x|β3, x|β1, x|β3, x|β4, x|β46);*?*?x|β6, 
 3356  x|β6, x|β6, x|β2, x|β1, x|β3, x|β3, x|β1, x|β3, 
 3364  x|β4, x|β4); A[j]|4α=↓|4D[j|4α+↓|411], B[j]|4α=↓|4D[j|4α_↓|4
 3367  48], C[j]|4α=↓|4D[j|4α_↓|4491].|'{A3}|≡2|≡1|≡.|9|4|πIf 
 3370  |ε0|4|¬E|4b|β1b|β2b|β3|4|¬W|46, |πset |εX|5|¬L|5A[b|β1b|β2b|
 3372  β3]; |πif 48|4|¬E|4|εb|β1b|β2b|β3b|β4b|β5b|β6|4|¬W|463, 
 3375  |πset |εX|5|¬L|5B[b|β1b|β2b|β3b|β4b|β5b|β6]; 
 3377  |πif 504|4|¬E|4|εb|β1b|β2b|β3b|β4b|β5b|β6b|β7b|β8b|β9]; 
 3379  |πotherwise _nd the smallest |εj |πsuch that 
 3386  |εU|4|¬W|4P[j], |πand set |εX|5|¬L|5x|βj. |πHere|'
 3391  {A9}!!(|εA[0],|4.|4.|4.|4,|4A[5])|4|∂α=↓|4(x|β3,|4x|β6,|4x|β
 3391  6,|4x|β1,|4x|β2,|4x|β3);|h|4x|β2,|4x|β2,|4x|β5,|4x|β5,|4x|β5
 3391  ,|4x|β6,|4x|β6,|4x|β6,|4x|β6|E|n|'{A11}| (B[48],|4.|4.|4.|4,
 3392  |4B[62])|4|Lα=↓|4(|εx|β4,|4x|β5,|4x|β6,|4x|β1,|4x|β1,|4x|β1,
 3392  |4x|β2,|4x|β2,|4x|β5,|4x|β5,|4x|β5,|4x|β6,|4x|β6,|4x|β6,|4x|
 3392  β6);>| (|εC[504],|4.|4.|4.|4,|4C[509])|4|Lα=↓|4(|εx|β1,|4x|β
 3393  3,|4x|β3,|4x|β3,|4x|β4,|4x|β4).>{A9}|πAnd |εP[1]|4α=↓|4|f510
 3395  |d3512|)|4α+↓|4|≤e|β1, P[2]|4α=↓|4|f510|d3512|)|4α+↓|4|≤e|β1
 3396  |4α+↓|4|≤e|β2,|4.|4.|4.|4,|4P[6]|4α=↓|4|f510|d3512|)|4α+↓|4|
 3396  ≤e|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|≤e|β6|4α=↓|41. 
 3397  |πThis makes 33 table entries; strictly speaking, 
 3404  howevjjr,*?*?|4α+↓|4|≤e|β1|4α+↓|4|≤e|β2,|4.|4.|4.|4,|4P[6]|4α=
 3404  ↓|4|f510|d3512|)|4α+↓|4|≤e|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|≤e|
 3404  β6|4α=↓|41. |πThis makes 33 table entries; strictly 
 3411  speaking, however, the elements |εx|βj |πshould 
 3417  also be considered auxiliary table entries, since 
 3424  we say ``set |εX|5|¬L|5x|βj'' |πin the algorithm. 
 3431  The |εx|βj-|πtable appears as the last three 
 3438  entries of |εA |πand the _rst three entries of 
 3447  |εB, |πso we arrange to have these tables adjacent 
 3456  in the computer memory. Further overlap is also 
 3464  possible, as in exercise 20. Note that the technique 
 3473  considered in this exercise is essentially the 
 3480  ``rectangle'' part of the rectangle-wedge-tail 
 3485  method.|'{A3}|≡2|≡2|≡.|9|4(|πSolution by G. Marsaglia.) 
 3490  Consider the ``continuous Poisson distribution'' 
 3495  |εG(x)|4α=↓|4|¬J|ur|¬X|)|≤m|)|4e|gα_↓|gtt|gx|gα_↓|g1|4dt/|≤)
 3495  (x), |πfor |εx|4|¬Q|40; |πif |εX |πhas this distribution 
 3503  then |"l|εX|"L |πis Poisson distributed, since 
 3509  |εG(x|4α+↓|41)|4α_↓|4G(x)|4α=↓|4e|gα_↓|g|≤m|≤m|gx/x*3. 
 3510  |πIf |ε|≤m |πis large, |εG |πis approximately 
 3517  normal, hence |εG|gα_↓|g1{H11}({H9}F(x){H11}){H9} 
 3520  |πis approximately linear, where |εF(x) |πis 
 3526  the normal distribution function (9). Let |εg(x) 
 3533  |πbe an e∃ciently computable function such that 
 3540  |¬G|εG|gα_↓|g1{H11}({H9}F(x){H11}){H9}|4α_↓|4g(x)|¬G|4|¬W|4|
 3540  ≤e |πfor |ε|→α_↓|¬X|4|¬W|4x|4|¬W|4|¬X; |πwe can 
 3545  now generate Poisson deviates e∃ciently as follows: 
 3552  Generate a normal deviate |εX, |πand set |εY|5|¬L|5g(X), 
 3560  N|5|¬L|5|"lY|"L, M|5|¬L|5|"lY|4α+↓|4|f1|d32|)|"L. 
 3562  |πIf |¬G|εY|4α_↓|4M|¬G|4|¬Q|4|≤e, |πoutput |εN; 
 3566  |πotherwise output |εM|4α_↓|41 |πor |εM, |πaccording 
 3572  as |εG{H11}({H9}F(X){H11}){H9}|4|¬W|4M |πor not.|'
 3576  !!|2This approach applies also to the binomial 
 3583  distribution, with |εG(x)|4α=↓|4|¬J|ur1|)p|)|4u|gx|gα_↓|g1(1
 3585  |4α_↓|4u)|gn|gα_↓|gx|4du |≤)(t|4α+↓|41)/|≤)(x)|≤)(t|4α+↓|41|
 3586  4α_↓|4x), |πsince |"l|εG|gα_↓|g1(U)|"L |πis binomial 
 3591  with parameters (|εt,|4p) |πand |εG |πis approximately 
 3598  normal.|'|H*?*?*?{U0}{H9L11M29}W58320#Computer Programming|9(Kn
folio 710 galley 6
 3600  uth/Addison-Wesley)|9f. 710|9Answers|9g. 6a|'
 3603  {A6}|≡2|≡3|≡.|9|4|πYes. The second method calculates 
 3608  |¬Gcos|4|ε2|≤u|¬G, |πwhere |ε|≤u |πis uniformly 
 3613  distributed between 0 |πand |ε|≤p/2. (|πLet |εU|4α=↓|4r|4|πc
 3619  os|4|ε|≤u, V|4α=↓|4r|4|πsin|4|ε|≤u.)|'⊗|≡2|≡5|≡.|9|4|f21|d33
 3621  2|)|4α=↓|4(.10101)|β2. |πIn general, the binary 
 3626  representation is formed by using 1 for |→|↔I, 
 3634  0 |πfor |→|↔i, from left to right, then su∃xing 
 3643  1. This technique [cf. K. D. Tocher, |εJ. Roy. 
 3652  Stat. Soc. |π|≡B|≡-|≡1|≡6 (1954), 49] can lead 
 3659  to e∃cient generation of independent bits having 
 3666  a given probability |εp, |πas well as the geometric 
 3675  and binomial distributions.|'{A3}|≡2|≡6|≡.|9|4|π(a) 
 3679  True, |¬K|ε|βk|4|πPr(|εN|β1|4α=↓|4k)|πPr(|εN|β2|4α=↓|4n|4α_↓
 3680  |4k)|4α=↓|4e|gα_↓|g|≤m|r1|gα_↓|g|≤m|r2(|≤m|β1|4α+↓|4|≤m|β2)|
 3680  gn/n*3. (|πb) False, unless |ε|≤m|β2|4α=↓|40, 
 3685  |πsince, e.g., |εN|β1|4α_↓|4N|β2 |πcan be negative.|'
 3691  {A3}|≡2|≡7|≡.|9|4|πLet the binary representation 
 3695  of |εp |πbe |ε.b|β1b|β2b|β3|4.|4.|4.|4, |πand 
 3700  proceed as follows.|'{A3}{I3.1H}!!|2|≡B|≡1|≡.|9[Initialize.]
 3703   Set |εm|5|¬L|5t, N|5|¬L|50, j|5|¬L|51. (|πDuring 
 3709  this algorithm, |εm |πrepresents the number of 
 3716  simulated uniform deviates whose relation to 
 3722  |εp |πis still unknown, since they match |εp 
 3730  |πin their leading |εj|4α_↓|41 |πbits; and |εN 
 3737  |πis the number of simulated deviates known to 
 3745  be less than |εp.)|'{A3}!!|2|π|≡B|≡2|≡.|9[Look 
 3750  at next colunm of bits.] Generate a random integer 
 3759  |εM |πwith the binomial distribution (|εm,|4|f1|d32|)). 
 3765  (|πNow |εM |πrepresents the number of unknown 
 3772  deviates which fail to match |εb|βj.) |πSet |εm|5|¬L|5m|4α_↓
 3779  |4M, |πand if |εb|βj|4α=↓|41 |πset |εN|5|¬L|5N|4α+↓|4M.|'
 3785  {A3}!!|2|≡B|≡3|≡.|9[|πDone?] If |εm|4α=↓|40 |πor 
 3789  if |ε.b|βj|βα+↓|β1b|βj|βα+↓|β2|4.|4.|4.|4α=↓|40, 
 3791  |πthe algorithm terminates. Otherwise, set |εj|5|¬L|5j|4α+↓|
 3796  41 |πand return to step B2.|'{IC}{A3}!!|2[When 
 3803  |εb|βj|4α=↓|41 |πfor in_nitely many |εj, |πthe 
 3809  average number of iterations |εA|βt |πsatis_es|'
 3815  {A9}|εA|β0|4α=↓|40;!!A|βn|4α=↓|41|4α+↓|4|f1|d32|)n|4|↔k|uc|)
 3815  k|)|4|↔a|(n|d5k|)|↔sA|βk,!!|πfor|9|εn|4|¬R|41.|;
 3816  {A9}|πLetting |εA(z)|4α=↓|4|¬K|4A|βnz|gn/n*3, 
 3818  |πwe have |εA(z)|4α=↓|4e|gz|4α_↓|41|4α+↓|4A(|f1|d32|)z)e|gz|
 3820  g/|g2, |πhence |εA(z)e|gα_↓|gz|4α=↓|41|4α_↓|4e|gα_↓|gz|4α+↓|
 3822  4A(|f1|d32|)z)e|gα_↓|gz|g/|g2|4α=↓|4|¬K|βk|β|¬R|β0|4(1|4α_↓|
 3822  4e|gα_↓|gz|g/|g2|ik)|4α=↓|41|4α_↓|4e|gα_↓|gz|4α+↓|4|¬K|βn|β|
 3822  ¬R|β1|4z|gn(|→α_↓1)|gn|gα+↓|g1/n*3|4(2|gn|4α_↓|41), 
 3823  |πand|'{A9}{M36}|εA|βm|4α=↓|41|4α+↓|4|↔k|uc|)k|¬R1|)|4|↔a|(n
 3824  |d5k|)|↔s|4|((|→α_↓1)|gk|gα+↓|g1|d22|gk|4α_↓|41|)|4α=↓|41|4α
 3824  +↓|4|(V|βn|βα+↓|β1|d2n|4α+↓|41|)|4α=↓|4|πlg|4|εn|4α+↓|4|(|≤g
 3824  |d2|πln|42|)|4α+↓|4|f1|d32|)|4α+↓|4|εf|β0(n)|4α+↓|4O(n|gα_↓|
 3824  g1)|'{A9}{M29}|πin the notation of exercise 5.2.2<48.]|'
 3831  {A24}{H10L12}|∨S|∨E|∨C|∨T|∨I|∨O|∨∪|4|4|∨3|∨.|∨4|∨.|∨2|'
 3832  {A12}{H9L11}|5|5|≡1|≡.|9|4There are (|fN|4α_↓|4t|d5n|4α_↓|4m
 3834  |)) |πways to pick |εn|4α_↓|4m |πrecords from 
 3841  the last |εN|4α_↓|4t; (|f|εN|4α_↓|4t|4α_↓|41|d5n|4α_↓|4m|4α_
 3844  ↓|41|)) |πways to pick |εn|4α_↓|4m|4α_↓|41 |πfrom 
 3850  |εN|4α_↓|4t|4α_↓|41 |πafter selecting the (|εt|4α+↓|41)|πst 
 3855  item.|'{A3}|5|5|≡2|≡.|9|4Step S3 will never go 
 3861  to step S5 when the number of records ldft to 
 3871  be examined is equal to |εn|4α_↓|4m.|'{A24}|≡2|≡8|≡.|9|4|πWe
 3877   must have |εP|βj|4α=↓|4q|βj|4α+↓|4j/k, |πwhere 
 3882  |εq|βj|4α+↓|4|¬K|4|¬T1/k|4α_↓|4q|βi|4|¬G|4Q|βi|4α=↓|4x|βj|βα
 3882  +↓|β1|¬Y|4α=↓|4p|βj|βα+↓|β1 |πfor |ε0|4|¬E|4j|4|¬W|4k. 
 3885  |πTo _nd such |εq|βj, |πstart with |εq|βj |πunde_ned 
 3893  and|εr|βj|4α=↓|4p|βj|βα+↓|β1 |πfor |ε0|4|¬E|4j|4|¬W|4k; 
 3896  |πthen repeatedly do the following: Find |εi 
 3903  |πand |εj |πwith |εq|βi, q|βj |πunde_ned and 
 3910  |εr|βi|4|¬R|41/k|4|¬R|4r|βj; |πset |εq|βj|5|¬L|4r|βj, 
 3913  Q|βj|5|¬L|5x|βi|βα+↓|β1, r|βi|5|¬L|5r|βi|4α_↓|4(1/k|4α_↓|4r|
 3914  βj), r|βj|5|¬L|51/k. [|πcf. |εElectronics Letters 
 3919  |π|≡1|≡0|≡, 8 (1974), 127<128.]|'{A3}|≡2|≡9|≡.|9|4Generate 
 3924  a random point (|εy|β1,|4.|4.|4.|4,|4y|βn) |πon 
 3929  the unit sphere, and let |ε|≤r|4α=↓|4{H10}|¬H{H9}|v4|¬K|4a|β
 3934  ky|=|βk|g2|). |πGenerate an independent uniform 
 3939  deviate |εU, |πand if |ε|≤r|gn|gα+↓|g1U|4|¬W|4K{H10}|¬H{H9}|
 3943  v4a|=|βk|g2y|=|βk|g2|), |πoutput (|εy|β1/|≤r,|4.|4.|4.|4,|4y
 3945  |βn/|≤r); |πotherwise start over. Here |εK|g2|4α=↓|4min|¬T(|
 3950  ¬K|4a|βky|=|βk|g2)|gn|gα+↓|g1/(|¬K|4a|=|βk|g2y|=|βk|g2)|4|¬G
 3950  |4|¬K|4y|=|βk|g2|4α=↓|41|¬Y|4α=↓|4a|urnα_↓1|)n|)|6|πif|6|εna
 3950  |βn|4|¬R|4a|β1, (|εn|4α+↓|41)/(a|β2|4α+↓|4a|βn)|gn|gα+↓|g1(a
 3951  |β1a|βn/n)|gn |πotherwise.|'{A24}|5|5|≡3|≡.|9|4|πWe 
 3954  should not confuse ``conditional'' and ``unconditional'' 
 3960  probabilities. The quantity |εm |πdepends randomly 
 3966  on the selections which took place among the 
 3974  _rst |εt |πelements; if |πwe take the average 
 3982  over all possible choices which could have occurred 
 3990  among these elements, we will _nd (|εn|4α_↓|4m)/(N|4α_↓|4t) 
 3997  |πis exactly |εn/N |πon the average. For example, 
 4005  consider the second element; if the _rst element 
 4013  was selected in the sample (this happens with 
 4021  probability |εn/N), |πthe second element is selected 
 4028  with probability (|εn|4α_↓|41)/(N|4α_↓|41); |πif 
 4032  the _rst element was not selected, the second 
 4040  is selected with probability |εn/(N|4α_↓|41). 
 4045  |πThe overall probability of selecting the second 
 4052  element is (|εn/N)(n|4α_↓|41)/(N|4α_↓|41)|4α+↓|4(1|4α_↓|4n/N
 4054  )(n)/(N|4α_↓|41)|4α=↓|4n/N.|'{A3}|5|5|≡4|≡.|9|4|πFrom 
 4056  the algorithm,|'{A9}|εp(m,|4t|4α+↓|41)|4α=↓|4|↔a1|4α_↓|4|(n|
 4058  4α_↓|4m|d2N|4α_↓|4t|)|↔sp(m,|4t)|4α+↓|4|(n|4α_↓|4(m|4α_↓|41)
 4058  |d2N|4α_↓|4t|)|4p(m|4α_↓|41,|4t).|;{A9}|πThe 
 4060  desired formula can be proved by induction on 
 4068  |εt. |πIn particular, |εp(n,|4N)|4α=↓|41.|'{A3}|π|5|5|≡5|≡.|
 4072  9|4In the notation of exercise 4, the probability 
 4080  that |εt|4α=↓|4k |πat termination is |εq|βk|4α=↓|4p(|εn,|4k)
 4085  |4α_↓|4p(n,|4k|4α_↓|41)|4α=↓|4(|fk|4α_↓|41|d5n|4α_↓|41|))/(|
 4085  fN|d5n|)). |πThe average is |¬K|ε|β0|β|¬E|βk|β|¬E|βN|4kq|βk|
 4089  4α=↓|4(N|4α+↓|41)n/(n|4α+↓|41).|'{A3}|5|5|≡6|≡.|9|4|πSimilar
 4090  ly, |¬K|ε|β0|β|¬E|βk|β|¬E|βN|4k(k|4α+↓|41)q|βk|4α=↓|4(N|4α+↓
 4091  |42)(N|4α+↓|41)n/(n|4α+↓|42); |πthe variance 
 4094  is therefore (|εN|4α+↓|41)(N|4α_↓|4n)n/(n|4α+↓|42)(n|4α+↓|41
 4096  )|g2.|'{A3}|5|5|≡7|≡.|9|4|πSuppose the choice 
 4100  is |ε0|4|¬W|4x|β1|4|¬W|4x|β2|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|4x|βn|
 4101  4|¬E|4N. |πLet |εx|β0|4α=↓|40, x|βn|βα+↓|β1|4α=↓|4N|4α+↓|41.
 4104   |πThe choice is obtained with probability |εp|4α=↓|4|≥u|β1|
 4111  β|¬E|βt|β|¬E|βN|4p|βt, |πwhere|'{A9}|ε|∂p|βt|4α=↓|4|(N|4α_↓|
 4113  4(t|4α_↓|41)|4α_↓|4n|4α+↓|4m|d2N|4α_↓|4(t|4α_↓|41)|)!!|∂|πfo
 4113  r!!|εx|βm|4|¬W|4t|4|¬W|4x|βm|βα+↓|β1,|;{A4}|Lp|βt|4α=↓|4|(n|
 4114  4α_↓|4m|d2N|4α_↓|4(t|4α_↓|41)|)|L|πfor!!|εt|4α=↓|4x|βm|βα+↓|
 4114  β1.>{A9}|πThe denominator of the product |εp 
 4121  |πis |εN*3; |πthe numerator contains the terms 
 4128  |εN|4α_↓|4n, N|4α_↓|4n|4α_↓|41,|4.|4.|4.|4,|41 
 4130  |πfor those |εt'|πs which are not |εx'|πs, and 
 4138  the terms |εn,|4n|4α_↓|41,|4.|4.|4.|4,|41 |πfor 
 4142  those |εt'|πs which |εare x'|πs. Hence |εp|4α=↓|4(N|4α_↓|4n)
 4148  *3n*3/N*3. Example|*/:|\ n|4α=↓|43, N|4α=↓|48, (x|β1,|4x|β2,|4x|
 4152  β3,)|4α=↓|4(2,|43,|47); p|4α=↓|4|f5|d83|)|4|f3|d37|)|4|f2|d3
 4153  6|)|4|f4|d35|)|4|f3|d34|)|4|f2|d33|)|4|f1|d32|)|4|f1|d31|).|
 4153  '{A3}|5|5|≡9|≡.|9|4|πThe reservoir gets seven 
 4158  records: 1, 2, 3, 5, 9, 13, 16. The second, fourth, 
 4169  and seventh of these are selected, namely 2, 
 4177  5, 16.|'{A3}|≡1|≡0|≡.|9|4|πDelete step R6 and 
 4183  the variabbl∧l∧∧b∧bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
 4184  bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
 4184  bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
 4184  bbb∧b∧b∧b∧b∧b∧b∧b∧bbb∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧
 4184  b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧
 4184  b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧b∧bbl*?*?{U0}{H9L11M29
folio 715 galley 7
 4184  }W|π58320#Computer Programming|9(Knuth/Addison-Wesley)|9f. 
 4186  715|9Answers|9g. 7a|'{A6}|≡1|≡1|≡.|9|4Arguing 
 4189  as in Section 1.2.10, which considers the special 
 4197  case |εn|4α=↓|41, |πwe see that the generating 
 4204  function is|'{A9}|εG(z)|4α=↓|4z|gn|↔a|(1|d2n|4α+↓|41|)|4α+↓|
 4206  4|(n|d2n|4α+↓|41|)|4z|↔s|↔a|(2|d2n|4α+↓|42|)|4α+↓|4|(n|d2n|4
 4206  α+↓|42|)|4z|↔s|4|¬O|4|¬O|4|¬O|4|↔a|(N|4α_↓|4n|d2N|)|4α+↓|4|(
 4206  n|d2N|)|4z|↔s.|;{A9}|πThe mean is |εn|4α+↓|4|¬K|βn|β|¬W|βt|β
 4210  |¬E|βN(n/t)|4α=↓|4n(1|4α+↓|4H|βN|4α_↓|4H|βn); 
 4211  |πthe variance is |εn(H|βN|4α_↓|4H|βn)|4α_↓|4n|g2(H|1|ur(2)|
 4214  )N|)|4α_↓|4H|1|ur(2)|)n|)).|'{A3}|≡1|≡2|≡.|9|4(|πNote 
 4216  that |ε|≤p|gα_↓|g1|4α=↓|4(b|βtt)|4.|4.|4.|4(b|β33)(b|β22), 
 4218  |πso we seek an algorithm which goes from the 
 4227  representation of |ε|≤p |πto that for |ε|≤p|gα_↓|g1.) 
 4234  |πSet |εb|βj|5|¬L|5j |πfor |ε1|4|¬E|4j|4|¬E|4t. 
 4238  |πThen for |εj|4α=↓|42,|43,|4.|4.|4.|4,|4t (|πin 
 4242  this order) interchange |εb|βj|≠l|5b[a|βj]. |πFinally 
 4247  for |εj|4α=↓|4t,|4.|4.|4.|4,|43,|42 (|πin this 
 4251  order) set |εb[a|βj]|5|¬L|5b|βj. (|πThe algorithm 
 4256  is based on the fact that (|εa|βtt)|≤p|β1|4α=↓|4|≤p|β1{H11}(
 4262  {H9}b|βtt).{H11})|'{H9}{A3}|≡1|≡3|≡.|9|4|πRenumbering 
 4264  the deck 0,|41,|4.|4.|4.|4,|42n|4α_↓|42, |πwe 
 4268  _nd |εs |πtakes |εx |πinto (|ε2x)|πmod(|ε2n|4α_↓|41), 
 4274  c |πtakes |εx |πinto (|εx|4α+↓|41)|πmod(|ε2n|4α_↓|41). 
 4279  |πWe have (|εc |πfollowed by |εs)|4α=↓|4cs|4α=↓|4sc|g2. 
 4285  |πTherefore any product of |εc'|πs and |εs'|πs 
 4292  can be transformed into the form |εs|gic|gk. 
 4299  |πAlso |ε2|g|≤'|g(|g2|gn|gα_↓|g1|g)|4|"o|41 |π{H11}({H9}modu
 4301  lo (|ε2n|4α_↓|41){H11}){H9}; |πsince |εs|g|≤'|g(|g2|gn|gα_↓|
 4304  g1|g) |πand |εc|g2|gn|gα_↓|g1 |πare the idnetity 
 4310  permutation, at most (|ε2n|4α_↓|41)|≤'(2n|4α_↓|41) 
 4314  |πarrangements are possible. (The |εexact |πnumber 
 4320  of di=erent arrangements is (|ε2n|4α_↓|41)k, 
 4325  |πwhere |εk |πis the order of 2 modulo (|ε2n|4α_↓|41). 
 4334  |πFor if |εs|gk|4α=↓|4c|gj, |πthen |εc|gj |π_xes 
 4340  the card 0, so |εs|gk|4α=↓|4c|gj|4α=↓|4|πidentity.) 
 4345  For further details, see |εSIAM Review |π|≡3 
 4352  (1961), 293<297.|'{A3}|≡1|≡4|≡.|9|4Set |εY|βj|5|¬L|5j 
 4356  |πfor |εt|4α_↓|4n|4|¬W|4j|4|¬E|4t. |πThen for 
 4360  |εj|4α=↓|4t,|4t|4α_↓|41,|4.|4.|4.|4,|4t|4α_↓|4n|4α+↓|41 
 4361  |πdo the following operations: Set |εk|5|¬L|5|"ljU|"L|4α+↓|4
 4366  1. |πIf |εk|4|¬Q|4t|4α_↓|4n |πthen set |εX|βj|5|¬L|5Y|βk 
 4372  |πand |εY|βk|5|¬L|5Y|βj; |πotherwise if |εk|4α=↓|4X|βi 
 4377  |πfor some |εi|4|¬Q|4j (|πa symbol table algorithm 
 4384  could be used), then set |εX|βj|5|¬L|5Y|βi |πand 
 4391  |εY|βi|5|¬L|5Y|βj; |πotherwise set |εX|βj|5|¬L|5k. 
 4395  (|πThe idea is to let |εY|βt|βα_↓|βn|βα+↓|β1,|4.|4.|4.|4,|4Y
 4400  |βj |πrepresent |εX|βt|βα_↓|βn|βα+↓|β1,|4.|4.|4.|4,|4X|βj, 
 4403  |πand if |εi|4|¬Q|4j |πand |εX|βi|4|¬E|4t|4α_↓|4n 
 4408  |πalso to let |εY|βi |πrepresent |εX[X|βi], |πin 
 4415  the execution of Algorithm P.)|'{A24}{H10L12}|∨S|∨E|∨C|∨T|∨I
 4420  |∨O|∨N|4|4|∨3|∨.|∨5|'{A12}{H9L11}|5|5|≡1|≡.|9|4A 
 4422  |εb-|πary sequence, yes (cf. exercise 2); a [0,1) 
 4430  sequence, no (since only _nitely many values 
 4437  are assumed by the elements).|'{A3}|5|5|≡2|≡.|9|4It 
 4443  is 1-distributed and 2-distributed, but not 3-distributed 
 4450  (the binary number 111 never appears).|'{A3}|5|5|≡3|≡.|9|4Cf
 4456  . exercise 3.2.2<17; repeat the sequence there 
 4463  with a period of length 27.|'{A3}|5|5|≡4|≡.|9|4The 
 4470  sequence begins |f1|d33|), |f2|d33|), |f2|d33|), 
 4475  |f1|d33|), |f1|d33|), |f1|d33|), |f1|d33|), |f2|d33|), 
 4480  |f2|d33|), |f2|d33|), |f2|d33|), |f2|d33|), |f2|d33|), 
 4485  |f2|d33|), |f2|d33|), etc. When |εn|4α=↓|41, 
 4490  3, 7, 15,|4.|4.|4. |πwe have |ε|≤n(n)|4α=↓|41, 
 4496  1, 5, 5,|4.|4.|4. |πso that |ε|≤n(2|g2|gk|gα_↓|g1|4α_↓|41)|4
 4501  α=↓|4|≤n(2|g2|gk|4α_↓|41)|4α=↓|4(2|g2|gk|4α_↓|41)/3; 
 4502  |πhence |ε|≤n(n)/n |πoscillates between |f1|d33|) 
 4507  and approximately |f2|d33|), and no limit exists. 
 4514  So the probability is unde_ned.|'!!|2The methods 
 4521  of Section 4.2.4 show that a numerical value 
 4529  |εcan |πbe meaningfully assigned to Pr(|εU|βn|4|¬W|4|f1|d32|
 4534  ))|4α=↓|4Pr (leading digit of the radix-4 representation 
 4541  of |εn|4α+↓|41 |πis 1)|4α=↓|4log|β4|42|4α=↓|4|f1|d32|).|'
 4545  {A3}|5|5|≡5|≡.|9|4If |ε|≤n|β1(n), |≤n|β2(n), 
 4548  |≤n|β3(n), |≤n|β4(n) |πare the counts corresponding 
 4554  to the four probabilities, we have |ε|≤n|β1(n)|4α+↓|4|≤n|β2(
 4560  n)|4α=↓|4|≤n|β3(n)|4α+↓|4|≤n|β4(n) |πfor all 
 4563  |εn. |πSo the desired result follows by addition 
 4571  of limits.|'{A3}|5|5|≡6|≡.|9|4|πBy exercise 5 
 4576  and induction,|'{A9}Pr(|εS|βj(n)|6|πfor|6some|6|εj,|61|4|¬E|
 4578  4j|4|¬E|4k)|4α=↓|4|↔k|uc|)1|¬Ej|¬Ek|)|4|πPr{H11}({H9}|εS|βj(
 4578  n){H11}){H9}.|;{A9}|πAs |εk|5|¬M|5|→|¬X, |πthe 
 4582  latter is a monotone sequence bounded by 1, so 
 4591  it converges; and|'{A9}Pr{H11}({H9}|εS|βj(n)|6|πfor|6some|6|
 4594  εj|4|¬R|41{H11}){H9}|4|¬R|4|↔k|uc|)1|¬Ej|¬Ek|)|4|πPr|ε{H11}(
 4594  {H9}S|βj(n){H11})|;{H9}|πfor all |εk. |πFor a 
 4600  counterexample to equality, it is not hard to 
 4608  arrange things so that |εS|βj(n) |πis always 
 4615  true for |εsome j, |πyet Pr{H11}({H9}S|βj(n){H11}){H9}|4α=↓|
 4620  40 |πfor |εall j.|'{A3}|5|5|≡7|≡.|9|4|πLet |εp|βi|4α=↓|4|¬K|
 4625  βj|β|¬R|β1|4|πPr{H11}({H9}|εS|βi|βj(n){H11}){H9}. 
 4626  |πThe result of the preceding exercise can be 
 4634  generalized to Pr{H11}({H9}|εS|βj(n) |πfor some 
 4639  |εj|4|¬R|41{H11}){H9}|4|¬R|4|¬K|βj|β|¬R|β1|4|πPr{H11}({H9}S|
 4639  βj(n){H11}){H9}, |πfor |εany |πdisjoint statements 
 4644  |εS|βj(n). |πSo we have 1|4α=↓|4Pr{H11}({H9}|εS|βi|βj(n) 
 4649  |πfor some |εi, j|4|¬R|41{H11}){H9}|4|¬R|4|¬K|βi|β|¬R|β1|4|π
 4652  Pr{H11}({H9}|εS|βi|βj(n) |πfor some |εj|4|¬R|41{H11}){H9}|4|
 4655  ¬R|4|¬K|βi|β|¬R|β1|4p|βi|4α=↓|41, |πand hence 
 4658  Pr{H11}({H9}|εS|βi|βj(n) |πfor some |εj|4|¬R|41{H11}){H9}|4α
 4661  =↓|4p|βi. |πGiven |ε|≤e|4|¬Q|40, |πlet |εI |πbe 
 4667  large enough so that |¬K|ε|β1|β|¬E|βi|β|¬E|βI|4p|βi|4|¬R|41|
 4671  4α_↓|4|≤e. |πLet |ε|≤f|βi(N)|4α=↓|4(|πnumber 
 4674  of |εn |πwith |εS|βi|βj(n) |πtrue, for some |εj|4|¬R|41, 
 4682  1|4|¬E|4n|4|¬E|4N{H11}){H9}/N. |πWe have |¬K|ε|β1|β|¬E|βi|β|
 4685  ¬E|βI|4|≤f|βi(N)|4|¬E|41, |πand for all large 
 4690  enough |εN, |¬K|β2|β|¬E|βi|β|¬E|βI|4|≤f|βi(N)|4|¬R|4|¬K|β2|β
 4692  |¬E|βi|β|¬E|βI|4p|βi|4α_↓|4|≤e; |πhence |ε|≤f|β1(N)|4|¬E|41|
 4694  4α_↓|4|≤f|β2(N)|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4|≤f|βI(N)|4|¬E|41|
 4694  4α_↓|4p|β2|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4p|βI|4α+↓|4|≤e|4|¬E|41|
 4694  4α_↓|4(1|4α_↓|4|≤e|4α_↓|4p|β1)|4α+↓|4|≤e|4α=↓|4p|β1|4α+↓|42|
 4694  ≤e. |πThis proves Pr{H11}({H9}|εS|β1|βj(n), |πsome 
 4699  |εj|4|¬R|41{H11}){H9}|4|¬E|4p|β1|4α+↓|42|≤e; 
 4700  |πhence Pr{H11}({H9}|εS|β1|βj(n), |πsome |εj|4|¬R|41{H11}){H
 4703  9}|4α=↓|4p|β1, |πand the desired result holds 
 4709  for |εi|4α=↓|41. |πBy symmetry of the hypotheses, 
 4716  it holds for any value of |εi.|'{A3}{H9}|5|5|≡8|≡.|9|4|πAdd 
 4724  together the probabilities for |εj,|4j|4α+↓|4d,|4j|4α+↓|42d,
 4728  |4.|4.|4. |πin De_nition E.|'{A3}|5|5|≡9|≡.|E|'
 4733  |uw|πlim|4sup|uc|)|εn|¬|¬M|¬X|)|4(a|βn|4α+↓|4b|βn)|4|¬E|4|uw
 4733  |πlim|4sup|uc|)|εn|¬M|¬X|)|4a|βn|4α+↓|4|uw|πlim|4sup|uc|)|εn
 4733  |¬M|¬X|)|4b|βn;|;{A9}|πhence we get|'{A9}|uw|πlim|4sup|uc|)|
 4737  εn|¬M|¬X|)|4{H11}({H9}(y|β1|βn|4α_↓|4|≤a)|g2|4α+↓|4|¬O|4|¬O|
 4737  4|¬O|4α+↓|4(y|βm|βn|4α_↓|4|≤a)|g2{H11}){H9}|4|¬E|4m|≤a|g2|4α
 4737  _↓|42m|≤a|g2|4α+↓|4m|≤a|g2|4α=↓|40,|;{A9}|πand 
 4739  this can happen only if each (|εy|βj|βn|4α_↓|4|≤a) 
 4746  |πtends to zero.|'{A3}|≡1|≡0|≡.|9|4In the evaluation 
 4752  of the sum in Eq. (22).|'{A3}|≡1|≡1|≡.|9|4|¬D|εU|β2|βn|¬F 
 4759  |πis |εk-|πdistributed if |¬D|εU|βn|¬F |πis (2,|42|εk)-|πdis
 4764  tributed.|'{A3}|≡1|≡2|≡.|9|4Let |εf|1(x|β1,|4.|4.|4.|4,|4x|β
 4766  k)|4α=↓|41 |πif |εu|4|¬E|4|πmax(|εx|β1,|4.|4.NI*?|≡1|≡1|≡.|9|
 4768  4|¬D|εU|β2|βn|¬F |πis |εk-|πdistributed if |¬D|εU|βn|¬F 
 4773  |πis (2,|42|εk)-|πdistributed.|'{A3}|≡1|≡2|≡.|9|4Let 
 4776  |εf|1(x|β1,|4.|4.|4.|4,|4x|βk)|4α=↓|41 |πif |εu|4|¬E|4|πmax(
 4778  |εx|β1,|4.|4.|4.|4,|4x|βk)|4|¬W|4v, f|1(x|β1,|4.|4.|4.|4,|4x
 4779  |βk)|4α=↓|40 |πotherwise. Then apply Theorem 
 4784  B.|'{A3}|≡1|≡3|≡.|9|4Let|'{A9}{A14}|h|εp|βk|4|n|∂α=↓|4|πPr(|
 4786  εU|βn|βα_↓|β1|4|¬A|4[|≤a,|4|≤b),|6U|βn|4|¬A|4[|≤a,|4|≤b),|4.
 4786  |4.|4.|4,|4U|βn|βα+↓|βk|βα_↓|β2|4|¬A|4[|≤a,|4|≤b),|6U|βn|βα+
 4786  ↓|βk|βα_↓|β1|4{U0}{H10L12M29}W58320#Computer 
folio 717 galley 8
 4787  Programming|9(Knuth/Addison-Wesley)|9f. 717|9Answers|9g. 
 4789  8a|'{A6}It remains to translate this into the 
 4797  probability that |εf|1(n)|4α_↓|4f|1(n|4α_↓|41)|4α=↓|4k. 
 4800  |πLet |ε|≤n|βk(n)|4α=↓|4(|πnumber of |εj|4|¬E|4n 
 4804  |πwith |εf|1(j)|4α_↓|4f|1(j|4α_↓|41)|4α=↓|4k{H11}){H9}; 
 4806  |πlet |ε|≤m|βk(n)|4α=↓|4|π(number of |εj|4|¬E|4n 
 4810  |πwith |εU|βj |πthe beginning of a gap of length 
 4819  |εk|4α_↓|41); |πand let |ε|≤m(n) |πsimilarly 
 4824  count the number of |ε1|4|¬E|4j|4|¬E|4n |πwith 
 4830  |εU|βj|4|¬A|4[|≤a,|4|≤b). |πWe have|'{A8}|ε|≤n|βk(n)|4α=↓|4|
 4833  ≤m|βk{L11}({H9}f|1(n){L11}),!!|≤m{H11}({H9}f|1(n){H11}){H9}|
 4833  4α=↓|4n.|;{A9}|πAs |εn|5|¬M|5|→|¬X, |πand we 
 4838  _nd that|'{A9}|ε|≤n|βk(n)/n|4α=↓|4{H11}({H9}|≤m|βk(|1f|1(n))
 4840  /f|1(n){H11}){H9}|6|¬O|6{H11}({H9}f|1(n)/|≤m(f|1(n)){H11}){H
 4840  9}|5|¬M|5p|βk/p|4α=↓|4p(1|4α_↓|4p)|gk|gα_↓|g1.|;
 4841  [|πWe have only made use of the fact that the 
 4851  sequence is (|εk|4α+↓|41)-distributed.]|'{A3}|≡1|≡4|≡.|9|4|π
 4854  Let|'{A9}|εp|βk|4|∂α=↓|4|πPr(|εU|βn|6|πbegins|6a|6run|6of|6l
 4855  ength|6|εk)|'{A3}|Lα=↓|4|πPr(|εU|βn|βα_↓|β1|4|¬Q|4U|βn|4|¬W|
 4856  4|¬O|4|¬O|4|¬O|4|¬W|4U|βn|βα+↓|βk|βα_↓|β1|4|¬Q|4U|βn|βα+↓|βk
 4856  )>{A3}|Lα=↓|4|(1|d2(k|4α+↓|42)*3|)|4{H11}|↔a{H9}|↔a|(k|4α+↓|4
 4857  2|d51|)|↔s|↔a|(k|4α+↓|41|d51|)|↔s|4α_↓|4|↔a|(k|4α+↓|42|d51|)
 4857  |↔s|4α_↓|4|↔a|(k|4α+↓|42|d51|)|↔s|4α+↓|41{H11}|↔s{H9}>
 4858  {A3}|Lα=↓|4|(k|d2(k|4α+↓|41)*3|)|4α_↓|4|(k|4α+↓|41|d2(k|4α+↓|
 4858  42)*3|)>{A9}(|πcf. exercise 3.3.2<13). Now proceed 
 4864  as in the previous exercise to transfer this 
 4872  to Pr(|εf|1(n)|4α_↓|4f|1(n|4α_↓|41)|4α=↓|4k{H11}){H9}. 
 4874  [We have assumed only that the sequence is (|εk|4α+↓|42)-|πd
 4882  istributed.]|'{A3}|≡1|≡5|≡.|9|4For |εs, t|4|¬R|40 
 4886  |πlet|'{A9}|εp|βs|βt|4|∂α=↓|4|πPr(|εX|βn|βα_↓|β2|βt|βα_↓|β3|
 4887  4α=↓|4X|βn|βα_↓|β2|βt|βα_↓|β2|4|=|↔6α=↓|4X|βn|βα_↓|β2|βt|βα_
 4887  ↓|β1|4|=|↔6α=↓|4|¬O|4|¬O|4|¬O|4|=|↔6α=↓|4X|βn|βα_↓|β1|;
 4888  {A3}|L!!!!!|πand!!|εX|βn|4α=↓|4|¬O|4|¬O|4|¬O|4α=↓|4X|βn|βα+↓
 4888  |βs|4|=|↔6α=↓|4X|βn|βα+↓|βs|βα+↓|β1>{A3}|Lα=↓|4(|f1|d32|))|g
 4889  s|gα+↓|g2|gt|gα+↓|g3;>{A9}|πfor |εt|4|¬R|40 |πlet 
 4893  |εq|βt|4α=↓|4|πPr(|εX|βn|βα_↓|β2|βt|βα_↓|β2|4α=↓|4X|βn|βα_↓|
 4893  β2|βt|βα_↓|β1|4|=|↔6α=↓|4|¬O|4|¬O|4|¬O|4|=|↔6α=↓|4X|βn|βα_↓|
 4893  β1)|4α=↓|4(|f1|d32|))|g2|gt|gα+↓|g1. |πBy exercise 
 4896  7, Pr(|εX|βn |πis not beginning of a coupon set)|4α=↓|4|¬K|ε
 4904  |βt|β|¬R|β0|4q|βt|4α=↓|4|f2|d33|), |πPr(|εX|βn 
 4906  |πis beginning of coupon set of length |εs|4α+↓|42)|4α=↓|4|¬
 4913  K|βt|β|¬R|β0|4p|βs|βt|4α=↓|4|f1|d33|)(|f1|d32|))|gs|gα+↓|g1.
 4913   |πNow proceed as in exercise 13.|'{A3}|≡1|≡6|≡.|9|4(|πSolut
 4920  ion by R. P. Stanley.) Whenever the subsequence 
 4928  |εS|4α=↓|4(b|4α_↓|41), (b|4α_↓|42),|4.|4.|4.|4,|41,|40,|40,|
 4929  41,|4.|4.|4.|4, (b|4α_↓|42), (b|4α_↓|41) |πappears, 
 4933  a coupon set must end at the right of |εS, |πsince 
 4944  some coupon set is completed in the _rst half 
 4953  of |εS. |πWe now proceed to calculate the probability 
 4962  that a coupon set begins at position |εn |πby 
 4971  manipulating the probabilities that the last 
 4977  prior appearance of |εS |πends at position |εn|4α_↓|41, 
 4985  n|4α_↓|42, |πetc., as in exercise 15.|'{A3}|≡1|≡8|≡.|9|4Proc
 4991  eed as in the proof of Theorem A to calculate 
 5001  Pr and Pr.|'{A3}|≡2|≡1|≡.|9|4Pr(|εZ|βn|4|¬A|4M|β1,|4.|4.|4.|
 5004  4,|4Z|βn|βα+↓|βk|βα_↓|β1|4|¬A|4M|βk)|4α=↓|4p(M|β1)|4.|4.|4.|
 5004  4p(M|βk), |πfor all |εM|β1,|4.|4.|4.|4,|4M|βk|4|¬A|4|λ|λM.|'
 5008  {A3}|≡2|≡2|≡.|9|4|πIf the sequence is |εk-|πdistributed, 
 5013  the limit is zero by integration and Theorem 
 5021  B. Conversely, note that if |εf|1(x|β1,|4.|4.|4.|4,|4x|βk) 
 5027  |πhas an absolutely convergent Fourier series|'
 5033  {A9}|εf|1(x|β1,|4.|4.|4.|4,|4x|βk)|4α=↓|4|↔k|uc|)α_↓|¬X|¬Wc|
 5033  β1,|4.|4.|4.|4,|4c|βk|¬W|¬X|)|3a(c|β1,|4.|4.|4.|4,|4c|βk)|πe
 5033  xp(|ε2|≤pi(c|β1x|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4c|βkx|βk){H11}
 5033  ){H9},|;{A9}|≡1|≡9|≡.|9|4(|πSolution by T. Herzog.) 
 5038  Yes, e.g., the sequence |¬D|εU|β|¬l|βn|β/|β2|β|¬L|¬F 
 5043  |πwhen |¬D|εU|βn|¬F |πsatis_es R4 (or even its 
 5050  weaker version), cf. exercise 33.|'{A9}we have|'
 5057  {A9}|uw|πlim|uc|)|.|εN|¬M|¬X|)|4|(1|d2N|)|4|↔k|uc|)0|¬En|¬WN
 5057  |)|4f|1(U|βn,|4.|4.|4.|4,|4U|βn|βα+↓|βk|βα_↓|β1)|4α=↓|4a(0,|
 5057  4.|4.|4.|4,|40)|4α+↓|4|≤e|βr,|;{A6}|πwhere|'{A6}|ε|¬G|≤e|βr|
 5059  ¬G|4|¬E|4|↔k|uc|)|¬Gc|β1|¬G,|4.|4.|4.|4,|4|¬Gc|βk|¬G|¬Qr|)|3
 5059  |¬Ga(c|β1,|4.|4.|4.|4,|4c|βk)|¬G,|;{A9}|πso |ε|≤e|βr 
 5062  |πcan be made arbitrarily small; hence this limit 
 5070  is equal to |εa(0,|4.|4.|4.|4,|40)|4α=↓|4|¬J|ur1|)0|)|4|¬O|4
 5073  |¬O|4|¬O|4|¬J|ur1|)0|)|4f(x|β1,|4.|4.|4.|4,|4x|βk)|4dx|β1|4.
 5073  |4.|4.|4dx|βk. |πSo Eq. (8) holds for all su∃ciently 
 5081  smooth functions |εf. |πThe remainder of the 
 5088  proof shows that the function in (9) can be approximated 
 5098  by smooth functions to any desired accuracy.|'
 5105  {A3}|≡2|≡3|≡.|9|4See |εAMM |≡7|≡5 (1968), 260<264.|'
 5110  {A3}|≡2|≡4|≡.|9|4|πThis follows immediately from 
 5114  exercise 22.|'{A3}|≡2|≡5|≡.|9|4If the sequence 
 5119  is equidistributed, the denominator in Corollary 
 5125  S approaches |f1|d312|), and the numerator approaches 
 5132  the quantity in this exercise.|'{A3}|≡2|≡6|≡.|9|4See 
 5138  |εMath. Comp. |π|≡1|≡7 (1963), 50<54. [Consider 
 5144  also the following example by A. G. Waterman: 
 5152  Let |¬D|εU|βn|¬F |πbe an equidistributed [0,|41) 
 5158  sequence and |¬D|εX|βn|¬F |πan |→|¬X-distributed 
 5163  binary sequence. Let |εV|βn|4α=↓|4U|β|"p|β|¬H|βn|β|"P 
 5167  |πor 1|4α_↓|4|εU|β|"p|β|¬H|βn|β|"P |πaccording 
 5170  as |εX|βn |πis 0 or 1. Then |¬D|εV|βn|¬F |πis 
 5179  equidistributed and white, but Pr(|εV|βn|4α=↓|4V|βn|βα+↓|β1)
 5183  |4α=↓|4|f1|d32|)*3 |πFurthermore let |εW|βn|4α=↓|4V|βn)|πmod 
 5187  1 where |¬D|ε|≤e|βn|¬F |πis any sequence that 
 5194  decreases monotonically to 0; then |¬D|εW|βn|¬F 
 5200  |πis equidistributed and white, yet Pr(|εW|βn|4|¬W|4W|βn|βα+
 5205  ↓|β1)|4α=↓|4|f3|d34|).]|'{A3}|≡2|≡8|≡.|9|4|πLet 
 5207  |¬D|εU|βn|¬F |πbe |→|¬X-|πdistributed, and use 
 5212  the sequence |¬D|f1|d32|)(|εX|βn|4α+↓|4U|βn)|¬F. 
 5215  |πThis is 3-distributed, using the fact that 
 5222  |¬D|εU|βn|¬F |πis (16,|43)-distributed.|'|≡2|≡9|≡.|9|4If 
 5226  |εx|4α=↓|4x|β1x|β2|4.|4.|4.|4x|βt |πis any binary 
 5230  number, we can consider the number |ε|≤n|urE|)x|)(n) 
 5237  |πof times |εX|βp|4.|4.|4.|4X|βp|βα+↓|βt|βα_↓|β1|4α=↓|4x, 
 5240  |πwhere |ε1|4|¬E|4p|4|¬E|4n |πand |εp |πis even. 
 5246  Similary, let |ε|≤n|urO|)x|)(n) |πcount the number 
 5252  of times when |εp |πis odd. Let |ε|≤n|urE|)x|)(n)|4α+↓|4|≤n|
 5259  urO|)x|)(n). |πNow|'{A9}|ε|≤n|urE|)0|)(n)|4α=↓|4|↔k|4|≤n|urE
 5261  |)0|≤⊂|≤⊂|4.|4.|4.|4|≤⊂|)(n)|4|¬V|4|↔k|4|≤n|urO|){J2}|≤⊂0{J2
 5261  }|≤⊂|4.|4.|4.|4{J2}|≤⊂|)(n)|4|¬V|4|↔k|4|≤n|urE|){J2}|≤⊂{J2}|
 5261  ≤⊂0|4.|4.|4.|4{J2}|≤⊂|)(n)|4|¬V|4|¬O|4|¬O|4|¬O|4|¬V|4|↔k|4|≤
 5261  n|urO|){J2}|≤⊂{J2}|≤⊂{J2}|≤⊂|4.|4.|4.|40(n)|;
 5262  {A9}|πwhere the |ε|≤n'|πs in these summations 
 5268  have |ε2k |πsubscripts, where asterisks denote 
 5274  summation over all |ε2|g2|gk|gα_↓|g1 |πcombinations 
 5279  of zeros and ones, and where ``|→|¬V'' denotes 
 5287  approximate equality (except for an error of 
 5294  at most |ε2k |πdue to end conditions). Therefore 
 5302  we _nd that|'{A9}{M36}|ε|(1|d2n|)|42k|≤n|urE|)0|)(n)|4α=↓|4|
 5305  (1|d2n|)|4|↔a|↔k|4|≤n|β|≤⊂|β0|β|≤⊂|β|4|β.|β|4|β.|β|4|β.|β|4|
 5305  β|≤⊂(n)|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|↔k|4|≤n|β|≤⊂|β|≤⊂|β|≤⊂|β|
 5305  4|β.|β|4|β.|β|4|β.|β|4|β0(n)|↔s|4α+↓|4|(1|d2n|)|4|↔k|uc|)|πa
 5305  ll|4|εx|)|4{H11}({H9}r(x)|4α_↓|4s(x){H11}){H9}|≤n|urE|)x|)(n
 5305  )|4α+↓|4O|↔a|(1|d2n|)|↔s,|'{A9}{M29}|πwhere |εx|4α=↓|4x|β1|4
 5307  .|4.|4.|4x|β2|βk |πcontains |εr(x) |πzeros in 
 5312  odd positions and |εs(x) |πzeros in even positions. 
 5320  By (|ε2k)-|πdistribution, the parenthesized quantity 
 5325  tends to |εk(2|g2|gk|gα_↓|g1)/2|g2|gk|4α=↓|4k/2. 
 5328  |πThe remaining sum is clearly a maximum if |ε|≤n|urE|)x|)(n
 5336  )|4α=↓|4|≤n|βx(n) |πwhen |εr(x)|4|¬Q|4s(x), |πand 
 5340  |ε|≤n|urE|)x|)(n)|4α=↓|40 |πwhen |εr(x)|4|¬W|4s(x). 
 5343  |πSo the maximum of the right-hand side becomes|'
 5351  {A9}|ε|(k|d22|)|4α+↓|4|↔k|uc|)0|¬Es|¬Wr|¬Ek|)|3(r|4α_↓|4s)|↔
 5351  a|(k|d5r|)|↔s|↔a|(k|d5s|)|↔s|↔h2|g2|gk|4α=↓|4|(k|d22|)|4α+↓|
 5351  4k|↔a|(2k|4α_↓|41{U0}{H9L11M29}W58320#Computer 
folio 720 galley 9
 5352  Programming|9(Knuth/Addison-Wesley)|9f. 720|9Answers|9g. 
 5354  9a|'{A6}|πNow Pr(|εX|β2|βn|4α=↓|40)|4|¬E|4|πlim|4sup|ε|βn|β|
 5356  ¬M|β|¬X|4|≤n|urE|)0|)(2n)/n, |πso the proof is 
 5361  complete. |εNote|*/:|'{A9}|\|↔k|uc|)r,s|)|4|↔a|(n|d5r|)|↔s|↔a
 5363  |(n|d5s|)|↔s|πmax(|εr,|4s)|4α=↓|42n2|g2|gn|gα_↓|g2|4α+↓|4n|↔
 5363  a|(2n|4α_↓|41|d5n|)|↔s;|;{A4}|↔k|uc|)r,s|)|4|↔a|(n|d5r|)|↔s|
 5364  ↔a|(n|d5s|)|↔s|πmin(|εr,|4s)|4α=↓|42n2|g2|gn|gα_↓|g2|4α_↓|4n
 5364  (|(2n|4α_↓|41|d5n|)|↔s.|;{A9}|π|≡3|≡0|≡.|9|4Let 
 5366  |εf|1(x|β1,|4x|β2,|4.|4.|4.|4,|4x|β2|βk)|4α=↓|4|πsign(|εx|β1
 5366  |4α_↓|4x|β2|4α+↓|4x|β3|4α_↓|4x|β4|4α+↓|4|¬O|4|¬O|4|¬O|4α_↓|4
 5366  x|β2|βk). |πConstruct a directed graph with |ε2|g2|gk 
 5373  |πnodes labeled (|εE;|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|β1) 
 5376  |πand (|εO;|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|β1), 
 5378  |πwhere each |εx |πis either 0 or 1. Let there 
 5388  be |ε1|4α+↓|4f|1(x|β1,|4x|β2,|4.|4.|4.|4,|4x|β2|βk) 
 5390  |πdirected arcs from (|εE;|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|
 5393  β1) |πto (|εO;|4x|β2,|4.|4.|4.|4,|4|εx|β2|βk), 
 5396  |πand |ε1|4α_↓|4f|1(x|β1,|4x|β2,|4.|4.|4.|4,|4x|β2|βk) 
 5398  |πdirected arcs leading from (|εO;|4x|β1,|4.|4.|4.|4,|4x|β2|
 5402  βk|βα_↓|β1) |πto (|εE;|4x|β2,|4.|4.|4.|4,|4x|β2|βk). 
 5405  |πWe _nd each node has the same number of arcs 
 5415  leading into it as those leading out; for example, 
 5424  (|εE;|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|β1) |πhas 
 5426  |ε1|4α_↓|4f|1(0,|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|β1)|4α+↓|4
 5426  1|4α_↓|4f|1(1,|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|β1) 
 5427  |πleading in and |ε1|4α+↓|4f|1(x|β1,|4.|4.|4.|4,|4x|β2|βk|βα
 5430  _↓|β1,|40)|4α+↓|41|4α+↓|4f|1(x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓
 5430  |β1,|41) |πarcs leading out, and |εf|1(x,|4x|β1,|4.|4.|4.|4,
 5435  |4x|β2|βk|βα_↓|β1)|4α=↓|4|→α_↓f|1(x|β1,|4.|4.|4.|4,|4x|β2|βk
 5435  |βα_↓|β1,|4x). |πDrop all nodes which have no 
 5442  paths leading either in or out, i.e., (|εE;|4x|β1,|4.|4.|4.|
 5449  4,|4x|β2|βk|βα_↓|β1) |πif |εf|1(0,|4x|β1,|4.|4.|4.|4,|4x|β2|
 5451  βk|βα_↓|β1)|4α=↓|4|→α+↓1, |πor (|εO;|4x|β1,|4.|4.|4.|4,|4x|β
 5453  2|βk|βα_↓|β1) |πif |εf|1(1,|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓
 5455  |β1)|4α=↓|4|→α_↓1. |πThe resulting directed graph 
 5460  is seen to be connected, since we can get from 
 5470  any node to (|εE;|41,|40,|41,|40,|4.|4.|4.|4,|41) 
 5474  |πand from this to any desired node. By Theorem 
 5483  2.3.4.2G, there is a cyclic path traversing each 
 5491  arc; this path has length |ε2|g2|gk|gα+↓|g1, 
 5497  |πand we may assume it starts at node (|εE;|40,|4.|4.|4.|4,|
 5505  40). |πConstruct the cyclic sequence with |εX|β1|4α=↓|4|¬O|4
 5511  |¬O|4|¬O|4α=↓|4X|β2|βk|βα_↓|β1|4α=↓|40, |πand 
 5513  |εX|βn|βα+↓|β2|βk|βα_↓|β1|4α=↓|4x|β2|βk |πif 
 5515  the |εn|πth arc of the path is from (|εE;|4x|β1,|4.|4.|4.|4,
 5523  |4x|β2|βk|βα_↓|β1) |πto (|εO;|4x|β2,|4.|4.|4.|4,|4x|β2|βk) 
 5526  |πor from (|εO;|4x|β1,|4.|4.|4.|4,|4x|β2|βk|βα_↓|β1) 
 5529  |πto (|εE;|4x|β2,|4.|4.|4.|4,|4x|β2|βk). |πFor 
 5532  example, the graph for |εk|4α=↓|42 |πis shown 
 5539  in Fig. A<5; the arcs of the cyclic path are 
 5549  numbered from 1 to 32, and the cyclic sequence 
 5558  is (00001000110010101001101110111110)(000|4.|4.|4.). 
 5560  Note that Pr(|εX|β2|βn|4α=↓|40)|4α=↓|4|f11|d316|) 
 5563  |πin this sequence. The sequence is clearly (|ε2k)-|πdistrib
 5570  uted, since each (|ε2k)-|πtuple |εx|β1x|β2|4.|4.|4.|4x|β2|βk
 5574   |πoccurs |ε1|4α+↓|4f|1(x|β1,|4.|4.|4.|4,|4x|β2|βk)|4α+↓|41|
 5576  4α_↓|4f|1(x|β1,|4.|4.|4.|4,|4x|β2|βk)|4α=↓|4|πtimes 
 5577  in the cycle. The fact that Pr(|εX|β2|βn|4α=↓|40) 
 5584  |πhas the desired value comes from the fact that 
 5593  the maximum value on the right-hand side in the 
 5602  proof of the preceding exercise has been achieved 
 5610  by this construction.|'{A6}{H9L11M29}|≡F|≡i|≡g|≡.|4|4|≡A|≡<|
 5613  ≡5|≡.|9|4|πDirected graph for the construction 
 5618  in exercise 30.|;{A6}{H10L12}{H9L11}|≡3|≡1|≡.|9|4Use 
 5622  Algorithm W with rule |ε|λR|π|β1 selecting the 
 5629  entire sequence.|'!!|2|εNote|*/: |\|πFor a generalization 
 5635  of this type of nonrandom behavior in |εR5-|πsequences, 
 5643  see Jean Ville, |ε|=⊂Etude Critique de la notion 
 5651  de Collectif (|πParis, 1939), 55<62. Perhaps 
 5657  |εR6 |πis also too weak, from this standpoint.|'
 5665  {A3}|≡3|≡2|≡.|9|4|πIf |ε|λR, |λR|¬S |πare computable 
 5670  subsequence rules, so is |ε|λR|¬C|4α=↓|4|λR|λR|¬S 
 5675  |πde_nes by the following functions: |εf|=|βn|¬C(|εx|β0,|4.|
 5680  4.|4.|4,|4x|βn|βα_↓|β1)|4α=↓|41 |πif and only 
 5684  if |λR de_nes the subsequence |εx|βr|m1,|4.|4.|4.|4,|4x|βr|m
 5689  k |πof |εx|β0,|4.|4.|4.|4,|4x|βn|βα_↓|β1, |πwhere 
 5693  |εk|4|¬R|40 |πand |ε0|4|¬E|4r|β1|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|4r
 5695  |βk|4|¬W|4n |πand |εf|=|βk|¬S(|εx|βr|m1,|4.|4.|4.|4,|4x|βr|m
 5697  k)|4α=↓|41.|'!!|2|πNow |¬D|εX|βn|¬F|λR|λR|¬S 
 5700  |πis (|¬D|εX|βn|¬F|λR)|λR|¬S. |πThe result follows 
 5705  immediately.|'{A3}|≡3|≡3|≡.|9|4Given |ε|≤e|4|¬Q|40, 
 5708  |π_ns |εN|β0 |πsuch that |εN|4|¬Q|4N|β0 |πimplies 
 5714  that both |¬G|ε|≤n|βr(N)/N|4α_↓|4p|¬G|4|¬W|4|≤e 
 5717  |πand |ε|¬G|≤n|βs(N)/N|4α_↓|4p|¬G|4|¬W|4|≤e. 
 5719  |πThen _nd |εN|β1 |πsuch that |εN|4|¬Q|4N|β1 
 5725  |πimplies that |εt|βN |πis |εr|βM |πor |εs|βM 
 5732  |πfor some |εM|4|¬Q|4N|β0. |πNow |εN|4|¬Q|4N|β1 
 5737  |πimplies that|'{A9}|ε|↔g|(|≤n|βt(N)|d2N|)|4α_↓|4p|↔g|4α=↓|4
 5739  |↔g|(|≤n|βr(N|βr)|4α+↓|4|≤n|βs(N|βs)|d2N|)|4α_↓|4p|↔g|4α=↓|4
 5739  |↔g|(|≤n|βr(N|βr)|4α_↓|4pN|βr|4α+↓|4|≤n|βs(N|βs)|4α_↓|4pN|βs
 5739  |d2N|βr|4α+↓|4N|βs|)|↔g|'{A9}|↔g|4|(|≤n|βt(N)|d2N|)|4α_↓|4p|
 5740  4|↔g|4α=↓|4|↔g|4|(|≤n|βr(N|βr)|4α+↓|4|≤n|βs(N|βs)|d2N|)|4α_↓
 5740  |4p|4|↔g|4α=↓|4|↔g|4|(|≤n|βr(N|βr)|4α_↓|4pN|βr|4α+↓|4|≤n|βs(
 5740  N|βs)|4α_↓|4pN|βs|d2N|βr|4α+↓|4N|βs|)|4|↔g|4|¬W|4|≤e.|;
 5741  {A9}|π|≡3|≡4|≡.|9|4For example, if the binary 
 5746  representation of |εt |πis 1|40|ε|gb|gα_↓|g2|41|40|ga|r1|41|
 5750  40|ga|r2|41|4.|4.|4.|41|40|ga|rk, |πwhere ``0|ε|ga'' 
 5753  |πstands for a sequence of |εa |πconsecutive 
 5760  zeros, let the rules |λR|ε|βt |πaccept |εU|βn 
 5767  |πif and only if |"l|εbU|βn|βα_↓|βk|"L|4α=↓|4a|β1,|4.|4.|4.|
 5771  4,|4|"lbU|βn|βα_↓|β1|"L|4α=↓|4a|βk.|'{A3}|≡3|≡5|≡.|9|4Let 
 5773  |εa|β0|4α=↓|4s|β0 |πand |εa|βm|βα+↓|β1|4α=↓|4|πmax|¬T|εs|βk|
 5775  4|¬G|40|4|¬E|4k|4|¬W|42|ga|rm|¬Y. |πConstruct 
 5777  a subsequence rule that selects element |εX|βn 
 5784  |πif and only if |εn|4α=↓|4s|βk |πfor some |εk|4|¬W|42|ga|rm
 5791  , |πwhen |εa|βm|4|¬E|4n|4|¬W|4a|βm|βα+↓|β1. |πThen 
 5795  lim|ε|βm|β|¬M|β|¬X|≤n(a|βm)/a|βm|4α=↓|4|f1|d32|).|'
 5796  {A3}|≡3|≡6|≡.|9|4|πLet |εb |πand |εk |πbe arbitrary 
 5802  but _xed integers greater than 1. Let |εY|βn|4α=↓|4|"lbU|βn|
 5809  "L. |πAn arbitrary in_nite subsequence |¬D|εZ|βn|¬F|4α=↓|4|¬
 5814  DY|βs|mn|¬F|λR |πdetermined by algorithms |λS 
 5819  and |λR (as in the proof of Theorem M) corresponds 
 5829  in a straightforward but notationally hopeless 
 5835  manner to algorithms |λS|¬S,|4|λR|¬S which inspect 
 5841  |εX|βt,|4X|βt|βα+↓|β1,|4.|4.|4.|4, X|βt|βα+↓|βs 
 5843  |πand/or select |εX|βt,|4X|βt|βα+↓|β1,|4.|4.|4.|4, 
 5846  X|βt|βα+↓|π|βm|βi|βn|β(|ε|βk|βα_↓|β1|β,|βs|β) 
 5847  |πof |¬D|εX|βn|¬F |πif and only if |λS and |λR 
 5856  inspect and/or select |εY|βs, |πwhere |εU|βs|4α=↓|40.X|βtX|β
 5861  t|βα+↓|β1|4.|4.|4.|4X|βt|βα+↓|βs. |πAlgorithms 
 5863  |λS|¬S and |λR|¬S determine an in_nite 1-distributed 
 5870  subsequence of |¬D|εX|βn|¬F |πand in fact (as 
 5877  in exercise 32) this subsequence is |→|¬X-distributed 
 5884  so it is (|εk,|41)-|πdistributed. Hence we _nd 
 5891  Pr(|εZ|βn|4α=↓|4a) |πand Pr(|εX|βn|4α=↓|4a) |πdi=er 
 5895  from 1/|εb |πby less than |ε1/2|gk.|'|Ha*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
 5901  
folio 722 galley 10
    0  {U0}{H9L11M29}|πW58320#Computer Programming|9(Knuth/Addison-
    1  Wesley)|9f. 722|9Answers|9g. 10a|'{A6}!!|2|εNote|*/: 
    5  |\|πThe result of this exercise is true if ``|εR6'' 
   14  |πis replaced consistently by ``|εR4'' |πor ``|εR5''; 
   21  |πbut it is false if ``|εR1'' |πis used, since 
   30  |εX(|fn|d52|)) |πmight be identically zero.|'
   35  {A3}|≡3|≡7|≡.|9|4|πFor |εn|4|¬R|42 |πreplace 
   38  |εU|βn|l2 |πby |f1|d32|)(|εU|βn|l2|4α+↓|4|≤d|βn), 
   41  |πwhere |ε|≤d|βn|4α=↓|40 |πor 1 according as 
   47  |¬T|εU|β(|βn|βα_↓|β1|β)|l2|βα+↓|β1,|4.|4.|4.|4,|4U|βn|l2|βα_
   47  ↓|β1|¬Y |πcontains an even or odd number of elements 
   56  less than |f1|d32|). [|εAdvances in Math. |π|≡1|≡4 
   63  (1974), 333<334.]|'{A3}|≡3|≡9|≡.|9|4|πSee |εActa 
   67  Arithmetica |π|≡2|≡1 (1972), 45<50. The best 
   73  possible value of |εc |πis unknown.|'{A3}|≡4|≡0|≡.|9|4If 
   80  every one-digit change to a random table yields 
   88  a random table, all tables are random (or none 
   97  are). If we don't allow degrees of randomness, 
  105  the answer must therefore be, ``Not always.''|'
  112  {A24}{H10L12}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|4|4|∨3|∨.|∨6|'
  113  {A12}{H9L11}|5|5|≡1|≡.|9|4|¬r|¬a|¬n|¬d|¬i!|h|∂|¬i|¬n|¬c|¬a!|
  113  ∂|¬x|¬r|¬a|¬n|¬d!!!!!!|∂rA|5|¬L|5(|εaX|4α+↓|4c)|πmod|4|εm.|E
  113  |n|'|L|π|¬s|¬t|¬j|L|¬9|¬f|Lstore|6exit|6location.>
  115  |L|¬s|¬t|¬a|L|¬8|¬f|LStore|6value|6of|6|εk.>|L|¬l|¬d|¬a|L|¬x
  116  |¬r|¬a|¬n|¬d|LrA|5|¬L|5|εX.>|L|π|¬m|¬u|¬l|L|¬7|¬f|LrAX|5|¬L|
  117  5|εaX.>|L|π|¬s|¬l|¬a|¬x|L|¬5|LrA|5|¬L|5(|εaX)|πmod|4|εm.>
  119  |L|π|¬i|¬n|¬c|¬a|L|¬1|LrA|5|¬L|5(|εaX|4α+↓|4c)|πmod|4|εm.>
  120  |L|π|¬s|¬t|¬a|L|¬x|¬r|¬a|¬n|¬d|LStore|6|εX.>|h!!|2|∂|π|¬x|¬r
  121  |¬a|¬n|¬d!|∂|¬j|¬n|¬o|¬v!|∂|¬3|¬1|¬4|¬1|¬5|¬9|¬2|¬6|¬2|¬1!!|
  121  9|∂Add|61,|6so|61|4|¬E|4|εY|4|¬E|4k.|E|n|'|L|L|π|¬m|¬u|¬l|L|
  122  ¬8|¬f|LrA|5|¬L|5|"l|εkX/m|"L.>|L|L|π|¬i|¬n|¬c|¬a|L|¬1|LAdd|6
  123  1,|6so|6|ε1|4|¬E|4|εY|4|¬Ek.>|L|π|¬9|¬h|L|¬j|¬n|¬o|¬v|L|≤α/↓
  124  |LReturn.>|L|L|¬j|¬m|¬p|L|≤α/↓|9|¬1>|L|¬x|¬r|¬a|¬n|¬d|L|¬c|¬
  126  o|¬n|L|¬1|LValue|6of|6|εX;|6X|β0|4α=↓|41.>|π|L|¬8|¬h|L|¬c|¬o
  127  |¬n|L|¬0|LTemp|6storage|6of|6|εk.>|L|π|¬7|¬h|L|¬c|¬o|¬n|L|¬3
  128  |¬1|¬4|¬1|¬5|¬9|¬2|¬6|¬2|¬1|LMultiplier,|7|εa.>
  129  {A3}|5|5|≡2|≡.|9|4|πPutting a random-number generator 
  133  into a program makes the results essentially 
  140  unpredictable to the programmer. If the behavior 
  147  of the machine on each problem were known in 
  156  advance, few programs would ever be written. 
  163  As Turing has said, the actions of a computer 
  172  quite often |εdo |πsurprise the programmer, especially 
  179  when he is debugging his program.|'{A24}{H10L12}|∨S|∨E|∨C|∨T
  185  |∨I|∨O|∨N|4|4|∨4|∨.|∨1|'{A12}{H9L11}|5|5|≡1|≡.|9|41010, 
  187  1011, 1000,|4.|4.|4.|4,|411000, 11001, 11110.|'
  191  {A3}|5|5|≡2|≡.|9|4(a)|9|→α_↓110001, |→α_↓11.001001001001|4.|
  192  4.|4.|4, 11.0010010000111111|4.|4.|4.|4.|'!!|2(b)|911010011,
  194   1101.001011001011|4.|4.|4.|4,|4111.011001000100000|4.|4.|4.
  195  |4.|'!!|2(c)|5|6|=∩11111, |=∩10.011011011011|4.|4.|4.|4, 
  198  10.011|=∩1111|=∩1|4.|4.|4.|4.|'!!|2(d)|9|→α_↓9.4, 
  200  |→α_↓|4.|4.|4.|47582417582413,|4.|4.|4.|4562951413.|'
  201  {A3}|5|5|≡3|≡.|9|41010113.2.|'{A3}|5|5|≡4|≡.|9|4(a) 
  203  Between rA and rX; (b) the remainder in rX has 
  213  radix point between bytes 3 and 4; the quotient 
  222  in rA ahs radix point one byte to the right of 
  233  the least signi_cant portion of the register.|'
  240  {A3}|5|5|≡5|≡.|9|4It has been subtracted from 
  245  999|4.|4.|4.|49|4α=↓|410|ε|gp|4α_↓|41, |πinstead 
  247  of from 1000|4.|4.|4.|40|4α=↓|410|ε|gp.|'{A3}|5|5|≡6|≡.|9|4(
  250  a) 2|gp|4α_↓|41, |→α_↓(2|gp|4α_↓|41); (|πb) |ε2|gp|gα_↓|g1|4
  254  α_↓|41, |→α_↓2|gp|gα_↓|g1; (|πc) |ε2|gp|gα_↓|g1|4α_↓|41, 
  258  |→α_↓(2|gp|gα_↓|g1|4α_↓|41).|'{A3}|5|5|≡7|≡.|9|4|πA 
  260  ten's complement representation for a negative 
  266  number |εx |πcan be obtained by considering |ε10|gn|4α+↓|4x 
  274  (|πwhere |εn |πis large enough for this to be 
  283  positive) and extending it on the left with in_nitely 
  292  many nines. The nines' complement representation 
  298  can be obtained in the usual manner. (These two 
  307  representations are equal for nonterminating 
  312  decimals, otherwise the nines' complement representation 
  318  has the form .|4.|4.|4|εa|π99999|4.|4.|4. while 
  323  the ten's complement representation has the form 
  330  .|4.|4.|4(|εa|4α+↓|41)0000|4.|4.|4.|4.) |πThese 
  332  representations may be considered sensible if 
  338  we regard the value of the in_nite sum |εN|4α=↓|49|4α+↓|490|
  346  4α+↓|4900|4α+↓|49000|4α+↓|4|¬O|4|¬O|4|¬O |πas 
  348  |→α_↓1, since |εN|4α_↓|410N|4α=↓|49.|'!!|2|πSee 
  352  also exercise 31, which considers |εp-|πadic 
  358  number systems. The latter agree with the |εp'|πs 
  366  complement notations considered here, for numbers 
  372  whose radix-|εp |πrepresentation is terminationg, 
  377  but there is no simple relation between the _eld 
  386  of |εp-|πadic numbers and the _eld of real numbers.|'
  395  {A3}|5|5|≡8|≡.|9|4|¬K|ε|βj|4a|βjb|gj|4α=↓|4|¬K|βj|4(a|βk|βj|
  395  βα+↓|βk|βα_↓|β1b|gk|gα_↓|g1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4a|βk|β
  395  j)b|gk|gj.|'{A3}|5|5|≡9|≡.|9|4|¬a |¬b|¬a|¬d |¬a|¬d|¬o|¬b|¬e 
  399  |¬f|¬a|¬c|¬a|¬d|¬e |¬f|¬a|¬d|¬e|¬d. (|εNote|*/: 
  402  |\|πOther possible ``number sentences'' would 
  407  be |¬d|¬o |¬a |¬d|¬e|¬e|¬d |¬a |¬d|¬e|¬c|¬a|¬d|¬e; 
  413  |¬a |¬c|¬a|¬d |¬f|¬e|¬d |¬a |¬b|¬a|¬b|¬e |¬b|¬e|¬e|¬f|¬, 
  419  |¬c|¬o|¬c|¬o|¬a|¬, |¬c|¬o|¬f|¬f|¬e|¬e; |¬b|¬o|¬b 
  422  |¬f|¬a|¬c|¬e|¬d |¬a |¬d|¬e|¬a|¬d |¬d|¬o|¬d|¬o.)|'
  426  |Hβ*?*?*?*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
  426